时间复杂度分析。操作者选择用于计数次数的线code同时运行的 [英] Time complexity analysis. choosing operator for counting number of times a line of code runs

问题描述

试析时间这个伪code的复杂性。在右边我担负起时代的每行的数量。我不知道是否使用日志N，N日志N，或者干脆n表示的同时，loop..please帮助

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

然后是的，你是在计算复杂性是正确的。该的code的复杂性确实是 O（nlogn）。

编辑：
虽然我很好奇，你是想在这里做什么。你是第一个计算的总和 N 元素 LOGN 倍。

Though I am curious what you are trying to do here. You are calculating the sum of 1st n elements logn times.

因此​​，返回值将像 N *（N + 1）/ 2 * LOGN

Hence the return value would be something like n*(n+1)/2 * logn

这篇关于时间复杂度分析。操作者选择用于计数次数的线code同时运行的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！