java - 这个简单程序的运行时间——时间复杂度

Question

我想弄清楚这个简单程序的时间复杂度是多少，但我似乎无法理解什么是最好的方法。

我已经并排写下了每一行的时间复杂度

1    public int fnA (int n) {                   
2      int sum = 0;                    O(1)
3      for (int i = 0; i < n; i++) {   O(n)
4        int j = i;                    O(n)
5        int product = 1;              O(1)
6      
7        while (j > 1) {               O(n)
8          product ∗= j;               O(log n) 
9          j = j / 2;                  O(log n)
10       }
11       sum += product;               O(1)
12     }
13     return sum;                     O(1)
14   }

我假设这些运行时间是否正确并且最终运行时间是:O(n)

如果不是，有人能解释我哪里出错了吗？

总体:

1 + n + n + 1 + n + logn + logn + 1 + 1
= 3n + 2logn + 4

Final: O(n)

Answer 1

该算法的时间复杂度为 O(NlogN)。

for 循环执行了 N 次(从 0 到 N)。

while 循环执行了 logN 次，因为您每次都将数字除以一半。

由于您正在执行 for 中的 while，因此您正在执行 logN 操作 N 次，从那里是 O(NlogN)。

您可以假设所有剩余的运算(赋值、乘法、除法、求和)都需要 O(1)