如何处理找到任何算法

Question

所有，

的大O /时间复杂度我一直觉得自己是值得怀疑的，当谈到找到一个给定的代码/算法的复杂性。防爆。

FOR I=1 TO N 
do J=1 
WHILE J*J < I 
do J=J+1 

上面的代码具有时间的Big Theta (N^(3/2))复杂性。但是，我不明白答案是如何得出的。

任何人都可以请指导我找到复杂的步骤或任何可以帮助我的具体资源吗？大部分的时间，我只能找到代码的复杂性N, lg N , N lg N和N^2

Answer 1

的方法始终是相同的：工作有多少业务正在为ñ的函数执行，然后扔掉低阶项和常量。

在你上面的例子

因此，内循环迭代大约SQRT（I）倍，所以我们有（约）SQRT（1） + SQRT（2） + SQRT（3） + ...结果是一个函数，其最高阶项是N ^（3/2）。