时间复杂度分析.选择用于计算一行代码运行次数的运算符

问题描述

分析这个伪代码的时间复杂度.在右边，我对每条线运行的次数进行了评估.我不确定是使用 log n 、 n log n 还是简单地 n 用于 while 循环..请帮助

Analysing time complexity of this pseudocode. On the right my take on the number of times each line runs. I'm not sure whether to use log n , n log n , or simply n for the while-loop..please help

                                times
1 sum = 0                        1
2 i = 1                          1
3 while i ≤ n                 log n + 1
4     for j = 1 to n           n log n
5     sum = sum + j            n log n
6 i = 2i                       log n
7 return sum                     1

这导致:2 n log + 2log n + 4

this results in: 2 n log + 2log n + 4

从而:O(n log n)

and thereby : O(n log n)

这是正确的吗?

推荐答案

如果你的 while 循环是:

If your while loop is:

3 while i < n                 log n + 1
4     for j = 1 to n           n log n
5        sum = sum + j         n log n
6     i = 2i                   log n

那么是的，您计算复杂性是正确的.代码的复杂度确实是O(nlogn).

Then yes, you are correct in calculating the complexity. The complexity of the code is indeedO(nlogn).

虽然我很好奇你在这里想做什么.您正在计算第 1 个 n 元素的总和 logn 次.

因此返回值将类似于 n*(n+1)/2 * logn

这篇关于时间复杂度分析.选择用于计算一行代码运行次数的运算符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！