algorithm - for i 的复杂度是多少：for o = i+1

Question

for i = 0 to size(arr)
   for o = i + 1 to size(arr)
      do stuff here

这个最坏的时间复杂度是多少？它不是 N^2，因为第二个在每个 i 循环中减一。不是N，应该更大。N-1 + N-2 + N-3 + ... + N-N+1。

Answer 1

它是 N ^ 2，因为它是两个线性复杂度的乘积。

（渐近复杂性被称为渐近而不相同是有原因的......）

请参阅Wikipedia 对所做简化的解释。

Answer 2

把它想象成你正在使用 anxn 矩阵。您正在处理矩阵中大约一半的元素，但 O(n^2/2) 与 O(n^2) 相同。

Answer 3

它n*(n-1)/2等于O(n^2)。

Answer 4

当你想确定一个算法的复杂度等级时，你只需要在算法的复杂度函数中找到增长最快的项。例如，如果你有复杂度函数f(n)=n^2-10000*n+400，要查找O(f(n))，你只需要在函数中找到“最强”项。为什么？因为n足够大，只有这个术语决定了整个函数的行为。话虽如此，很容易看出f1(n)=n^2-n-4和f2(n)=n^2都在O(n^2). 但是，对于相同的输入大小n，它们不会运行相同的时间。

在您的算法中，如果n=size(arr)，do stuff here代码将运行f(n)=n+(n-1)+(n-2)+...+2+1时间。很容易看出f(n)表示算术级数的总和，这意味着f(n)=n*(n+1)/2，即f(n)=0.5*n^2+0.5*n。如果我们假设do stuff here是O(1)，那么您的算法具有O(n^2)复杂性。

对于 i = 0 到 size(arr)

我假设循环在i大于size(arr)，不等于时结束。但是，如果是后者，则比f(n)=0.5*n^2-0.5*n，它仍然在O(n^2)。请记住O(1),O(n),0(n^2)，... 是复杂度类，算法的复杂度函数是描述对于输入大小 n，算法中有多少步的函数。