问题描述
试析时间这个伪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同时运行的的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!