algorithm - theta - o标记




为什么该算法的Big-O复杂度为O(n ^ 2)? (5)

即使我们在一开始就设置了j = n * n,我们还是在每次迭代过程中增加i并减少j,所以迭代的结果数目是否不应该比n * n小很多?

是! 这就是为什么它是O(n ^ 2)。 按照相同的逻辑,它比 n * n * n 很多 ,这使其变为O(n ^ 3)。 按照类似的逻辑,它甚至是O(6 ^ n)。

big-O为您提供有关上限的信息。

我相信您正在尝试询问为什么复杂度是theta(n)或omega(n),但是如果您只是想了解big-O是什么,那么您 真的 需要了解它首先给函数带来了 上限 ,最重要的。

我知道此算法的大O复杂度是 O(n^2) ,但我不明白为什么。

int sum = 0; 
int i = 1; j = n * n; 
while (i++ < j--) 
  sum++;

即使我们在开始时设置 j = n * n ,我们在每次迭代过程中都将i递增和j递减,因此得出的迭代次数是否不应该比 n*n 小很多?


big-O复杂度忽略系数。 例如: O(n)O(2n)O(1000n) 都是相同的 O(n) 运行时间。 同样, O(n^2)O(0.5n^2) 均为 O(n^2) 运行时间。

在您的情况下,实际上每次循环都会使循环计数器增加2(因为 j--i++ 具有相同的作用)。 因此,您的运行时间为 O(0.5n^2) ,但是与删除系数时的 O(n^2) 相同。


在每次迭代期间,您将 i 递增并递减 j ,这等效于将 i 递增2。因此,迭代的总数为n ^ 2/2,仍然为O(n ^ 2)。


您将精确地进行 n*n/2 循环迭代(如果 n 为奇数,则为 (n*n-1)/2 n )。 在大O表示法中,因为常量因子“不计算”,所以 O((n*n-1)/2) = O(n*n/2) = O(n*n)


是的,该算法为O(n ^ 2)。

为了计算复杂度,我们有一张表复杂度:

O(1)O(log n)O(n)O(n log n)
O(n²)O(n ^ a)O(a ^ n)O(n!)

每行代表一组算法。 一组算法在O(1)中,也在O(n)和O(n ^ 2)中,等等。但是不是相反的。 因此,您的算法实现了n * n / 2个句子。

O(n)<O(nlogn)<O(n * n / 2)<O(n²)

因此,因为O(n)和O(nlogn)较小,所以包含算法复杂度的一组算法为O(n²)。

例如:对于n = 100,总和=5000。=> 100 O(n)<200 O(n·logn)<5000(n * n / 2)<10000(n ^ 2)

对不起我的英语。





asymptotic-complexity