int sum=0;
for(int i=1;i<N;i*=2)
for(int j=0;j<N;j++)
sum++;
我从书上看到上面代码的时间复杂度是0 (nlogn)，但是我看不太懂。我希望有一个好的解释。
所以，基本上你是在添加矩阵(2D表)的一些单元格的值。单元格是行和列在一起的地方。I表示行号，j表示列号。在这个矩阵中，您忽略第一行，因为它以i=1开始(编程计数从0开始)。您首先将第二行中的单元格计数为一个数字(第一行作为程序员)。然后每次我们把行号乘以2。首先我们计算第[1]行上的单元格然后是第[2]行然后是第[4]行，第[8]行等等直到行号= n
我们能不能换个方法?
是的，我们可以用另一种更快的方法。如果我们用对数的数学函数(log(N))知道每行的列数(在我们的例子中是N)，我们加上1，因为我们不计算行[1]，我们可以找到我们想要计数的行数，并将其乘以每行的单元格数。所以最后的结果是:sum = (log(N) + 1) * N