runtime - 什么是总频率计数和运行时间(Big-O 表示法)？

Question

我有以下代码片段:

1. for (i = 1; i < n; i++) 
2.    for (j = 1; j < i*i; j++) 
3.      if(j % i == 0)
4.         for(k = 0; k < j;k++)
5.            sum++; 

什么是总频率计数和运行时间(Big-Oh 表示法)？

频率计数检查一段代码并预测要执行的指令数量(例如，对于每条指令，预测代码运行时每条指令会遇到多少次。)

我尝试通过以下方式进行分析:

Loop1 is executed n-1 times, then F.C. is 2n
Loop2 is executed (ii)-1 times, then F.C. is 3(ii)
total frequency count for loop1+loop2 is 2n + sum (from i=1 to n-1)3*i*i
I have a problem with if(j%i==0). What is loop execution here?
Loop4 is executed j times, then F.C. is 2j+2

Answer 1

前 2 行(i 和 j 循环)是 n^3。

第4行，第k个循环是n^2。我很想将它们相乘并表示 n^5。但你必须考虑第 3 行的 if 。

if 语句仅在每 i 次迭代中为真一次，因此您必须除以 i(即除以 n):(n^3)/n = n^2 给出 n^2 * n^2 = n^4。

O(n^4)