Nic*_*rin 4 c++ algorithm big-o analysis time-complexity
我正忙着做一项任务,我正在努力解决一个问题.我知道我不应该直接询问作业问题,所以我理解我是不是直截了当的答案.但无论如何这里仍然存在.
我们必须计算不同算法的运行时复杂度,我坚持的就是这个.
for(int i = 1 ; i < n ; i++)
for(int j = 0 ; j < i ; j +=2)
sum++;
现在根据我的理解,我的第一个想法是小于O(n 2),因为嵌套循环没有运行整整n次,并且j变量仍然每个循环递增2而不是像正常循环一样迭代.虽然,当我做了一些N = 10,N = 100,N = 1000等的代码模拟时,我输出sum变量时得到了以下结果.
N = 10 : 25,
N = 100 : 2500,
N = 1000 : 250000,
N = 10000 : 25000000
当我看到这些结果时,O符号似乎应该比O(n)大得多.
我们在赋值中给出的4个选项是:O(1),O(n 2),O(n)和O(logn).正如我之前所说,我看不出它如何像O(n 2)一样大,但结果却指向了这一点.所以我只是觉得我不完全理解这一点,或者我错过了一些链接.
任何帮助,将不胜感激!
luk*_*k32 11
Big O表示法不会为您提供操作数量.它只是告诉你它随着输入的增长会有多快.这就是你观察到的.
当您增加输入c时间时,操作总数会增加c^2.
如果你准确计算(几乎)精确的操作次数(n^2)/4.
当然你可以用总和来计算它,但是因为我不知道如何使用数学,所以我将给出一个"经验"的解释.简单的循环内循环具有相同的开始和结束条件n^2.这种循环产生用于所有可能组合的矩阵 "i"和"j".因此,如果start 1和end都N在两种情况下都可以获得N*N组合(或有效迭代).
但是,你的内循环是为了i < j.这基本上是这个正方形的三角形,这是第一个0.5因素,然后你跳过其他所有元素,这是另一个0.5因素; 乘以你得1/4.
并且O(0.25 * n^2) = O(n^2).有时人们喜欢将因子留在那里因为它可以让你比较具有相同复杂性的两种算法.但它并没有改变增长率n.