确定此算法的大O时间复杂度

Question

我正在尝试理解下面代码的Big-O。

代码的目的

本质上，我试图选择随机节点的子集（最大大小= selectionSize），以及它们之间存在的任何边。选择随机节点是在while循环中完成的。在完成此操作后，我想选择任何存在于所选节点之间的边缘。

我认为代码的时间复杂度和原因

我认为运行时间为O = n^2，其中n=selectionSize。原因是：即使我可以增加nodes中元素的大小（例如将其设置为10000），我也不认为它会影响算法，因为我只循环最大的selectionSize。我有点担心这是错误的唯一原因是while循环，在该循环中，我从列表中选择随机元素，直到达到所需数量。虽然这可能需要很长时间（因为它是随机的），但我认为它不会影响整体输出的时间。 编辑：呃，在重新考虑之后...算了... nodes的大小确实会影响它（因为node.getNeighbors()最多可以是nodes的大小）。因此，如果selectionSize等于nodes的大小，则运行时间为O=n^2，其中n=nodes的大小。

欢迎提供任何提示/建议。

代码

// nodes and selectionSize are my input:
int[] nodes = {1,2,3...,1000}; // 1000 elements
int selectionSize = 500; // This can be at most the size of the elements (in this case 1000)

run_algo(nodes, selectionSize);

public void run_algo(int[] nodes, int selectionSize) {
    randomNodesList = {};

    while(randomNodesList < selectionSize) {
        randomNode = selectRandomNode(nodes); // Assume O(1)

        if(!randomNodesList.exists(randomNode)) { // Assume O(1)
            randomNodesList.push_back(randomNode); // Assume O(1)
        }
    }

    foreach(node in randomNodesList) {
        foreach(neighbor in node.getNeighbors()) { // Max. nodes size (in this case 1000)
            if (!randomNodesList.exists(neighbor)) { // Assume O(1)
                AddEdge(node, neighbor); // Takes O(1) time
            }
        }
    }
}

- Moody

---

嗨@VidorVistrom，感谢您的评论。我已经编辑了我的帖子。如果还不清楚，请告诉我。 - Moody

很难说在随机抽取相同索引的最坏情况下会发生什么。你可以轻松地谈论最好的情况。这应该是线性的，取决于选择大小。因为你的查找是常数时间，n+n 仍然是线性的。 - Pushan Gupta

@VidorVistrom 谢谢您的见解和提示！ - Moody

Answer 1

如果selectRandomNode(nodes);带有重复选项（同一节点可能被选择两次），则大O为未定义，因为您可能会陷入无限循环（您可能会一遍又一遍地选择同一节点）。

如果没有重复选项，则是O(n^2)（在最坏的情况下，每个节点可能与每个其他节点相连）。

选择不重复的注意事项：

考虑当您拥有大小为n的数组A和一个空数组B时的情况。A中的所有元素都是唯一的。

任务是从A中随机选择n个元素填充B。期望在B中至少有k个唯一元素。

可以证明，拥有超过k个唯一项目的概率随着n的增加而增加（我已在图后添加了方程式）。

因此，在实践中，当n和k之间的差异增加时，循环在单次遍历（即少于n步）中完成的概率会变得更大。如果你仔细想想，这非常直观，数学只是锦上添花。

---

def k_numerator(n, k):
    res = 0
    sign = 1
    for i in range(k, 0, -1):
        pow_term = (i ** n)
        comb_term = comb(k, i)
        prod = pow_term * comb_term
        prod = prod * sign
        res = res + prod
        sign = sign * -1
    return res

def p_exactly_k(n, k):
    """ 
    Returns the probability of `B` containing exactly `k` unique elements
    (also see notes above)
    """

    return (comb(n, k) * k_numerator(n, k)) / (n ** n)

- axiom

Answer 2

我不确定我是否理解正确。但是让我们来分析一下： while-循环在最好和最坏的情况下都运行“selectionSize”次，n是节点的数量。

因此，randomNodeList的大小为O(n)。 在简单图中，您可以有O(n-1)个邻居。所以整个循环必须在O(n^2)中（因为n*(n-1)）

公理是正确的。实际上不可能找到该算法的上限。它是不确定的。这取决于您的随机数字。

- Andreas

---

非常感谢您的见解！ - Moody

while循环运行的次数取决于selectRandomNode()函数的实现。 - axiom