基本算法手册，需要澄清

Question

Integer: FindMedian(Integer: array[]) 
For i = 0 To array.Length - 1 
// Find the number of values greater than and less than array[i]. 

Integer: num_larger = 0 
Integer: num_smaller = 0 

For j = 0 To array.Length - 1
    If (array[j] < array[i]) 
        Then num_smaller = num_smaller + 1 
    If (array[j] > array[i]) 
        Then num_larger = num_larger + 1 Next j 
    If (num_smaller = num_larger) 
        Then Return array[i] 
    End If 
Next i 
End FindMedian

关于algoritm的复杂性，作者说：

如果数组包含N个值，则外部For i循环执行N次。对于这些迭代中的每一个，内部For j循环执行N次。这意味着内循环内的步骤执行N×N=N次，使算法的运行时间为O(N )。

我认为复杂性应该是O(N^2)。我说错了吗？

Answer 1

当然，顺序是o(N^2)，因为对于每个外部循环，您的内环将运行n个时间，因此有n个外循环。时间复杂度为o(n^2)。

你能把找到它的页码和书的链接分享一下吗？

Answer 2

是的，我想是的。

来自https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

O(N^2)表示其性能与输入数据集大小的平方成正比的算法。这在涉及对数据集的嵌套迭代的算法中很常见。更深层次的嵌套迭代将导致O(N^3)、O(N^4)等。

bool ContainsDuplicates(IList<string> elements)
{
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

这正是你想要的。