为什么执行 N/2 步的代码被认为是 O(N)？

Question

考虑一个嵌套循环。外循环从 i=0 开始迭代 N 次，内循环从 j=i+1 开始迭代 j=N 次。所以内循环将大致执行n/2步。然而，最后，运行时被认为是 O(N²) 为什么内部循环被认为是 O(N) 而不是 O(N/2)，因为我们还有其他具有 O(log n) 运行时间的代码？

Answer 1

Big-O notation 表示执行一段代码所花费的时间 复杂度 ，与某些指标成比例。通常，大括号中使用的符号表示输入大小、容器大小等数量

直觉上，O(N)是指一个码运行的次数与大括号内包含的符号的比例，如反对确切次它运行s。它在现实中可能运行 K = N/2 次，但点 Big-O 符号试图强调的事实是，K 的值是由 [=13= 的大小来估计的]是，并且与K.

成正比

为了进一步澄清，请注意对于足够大的 N，除以 2 并不重要，因为它只是一个常数因子。 对于足够大的 N，常量可以忽略不计 的概念对于理解和掌握各种复杂性符号（包括 Big-O.

至关重要）

Answer 2

您似乎混合两种不同的情况（最终公式-N**2/C中的除法-其中C 可以 ignored: O(N**2/C) == O(N**2); 和 loop 中的除法: for (int j = N; j >= 1; j /= C) where C 导致对数 ):

 for (int i = 1; i <= N; ++i)
   for (int j = i + 1; j <= N; ++j) 
     SomeOperation(i, j);

我们数一数要执行的SomeOperation(i, j)个数：

 i    j
-------------------
 1    N - 1
 2    N - 2
 3    N - 3
..
 N    0

所以我们有

(N - 1) + (N - 2) + ... + 2 + 1 + 0 ==
 N * (N - 1) / 2 == 
 N**2 / 2 - N / 2 ==
 O(N**2 / 2 - N / 2) == O(N**2 / 2) == O(N**2)

相反（请注意 j /= 2 而不是 ++j），这意味着 少得多 内循环

 for (int i = 1; i <= N; ++i)
   for (int j = N; j >= 1; j /= 2) 
     SomeOperation(i, j);

 i    j
-------------------
 1    log(N)
 2    log(N)
 3    log(N)
..
 N    log(N)

我们这里有

 log(N) + log(N) + ... + log(N) ==
 N * log(N) == 
 O(N * log(N))

为什么执行 N/2 步的代码被认为是 O(N)？

Why codes that does N/2 steps are considered O(N)?

algorithm

big-o