算法的大 O 复杂度

Question

我正在尝试找出算法的确切大 O 值。我举个例子：

for (int i = 0; i < n; i++) // 2N + 2
{
    for (int x = i; x < n; x++) // N * 2N + 2 ?
    {
        sum += i; // N
    }
} // Extra N?

所以如果我分解其中的一些，int i = 0 将是 O(1)，i < n 是 N+1，i++ 是 N，将内循环乘以 N:

2N+2+N(1+N+1+N)=2N^2+2N+2N+2=2N^2+4N+2

为循环终止和总和常数添加 N，= 3N^2 + 5N + 2...

基本上，我不是 100% 确定如何计算算法的 exact O 表示法，我的猜测是 O(3N^2 + 5N + 2)。

Answer 1

你说的准确是什么意思？大 O 是渐近上界，因此根据定义它是不精确的。

将 i=0 视为 O(1) 并将 i<n 视为 O(N+1) 是不正确的。相反，将外循环视为执行某件事 n 次，并且对于外循环的每次迭代，内循环至多执行 n 次。循环内的计算需要常数时间（计算不会随着 n 变大而变得更复杂）。所以你最终得到 O(n*n*1) = O(n^2)，二次复杂度。

当询问 [=21=] 时，您是运行从 0 到 n，然后从 1 到 n，然后从 2 到 n，...，从 (n- 1）对n，每次都做一个常数时间的操作。所以你做了 n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2 = n^2/2 + n/2 次迭代。要从精确的计算次数到大 O 表示法，省略常量和低阶项，最终得到 O(n^2)（省略 1/2 和 +n/2） .

Answer 2

大 O 表示最坏情况的复杂性。

这里最坏的情况只有在两个循环都运行 n 次即 n*n.

时才会发生

所以，复杂度是 O(n2)。

算法的大 O 复杂度

Big-O complexity of algorithms

big-o

computer-science