英文:
How to find T(n) of an algorithm
问题
k = 1 # 1
while (k <= n): # n + 1
j = 1 # n
while (j <= n): # log_2(n) + 1 ?
j *= 2 # log_2(n) ?
k += 1 # n
这个算法的时间复杂度 T(n) 可以表示为：
T(n) = n + 1 + n + (log₂(n) + 1) + log₂(n) + n
简化后：
T(n) = 3n + 2log₂(n) + 2
所以正确的时间复杂度应该是 T(n) = 3n + 2log₂(n) + 2。
英文:
k = 1 # 1
while (k <= n): # n + 1
j = 1 # n
while (j <= n): # log_2(n) + 1 ?
j *= 2 # log_2(n) ?
k += 1 # n
What would be T(n) of this algorithm? Would it be T(n) = 3n +2log_2 n + 3 ? Or would it be T(n) = 3n + 2n^2 + 3 ? All can find online is how to find O(n)
答案1
得分: 1
你对每个语句的数值都是正确的。所以只需将它们相加并相乘。
内部循环的T是
2 * log_2(n) + 1
添加j的初始化和k的增量以获得外部循环主体的T，如下所示
2 * log_2(n) + 3
外部循环执行了n次，结果是
n * 2 * log_2(n) + 3 * n
然后加1用于k的初始化，以及n + 1用于外部while条件的测试，所以最终的T是
n * 2 * log_2(n) + 3 * n + 2
英文:
Your values for each statement are correct. So just add them up and multiply.
The T of the inner loop is
2 * log_2(n) + 1
Add the initialization of j and increment of k to get the T of the body of the outer loop as
2 * log_2(n) + 3
This is executed n times by the outer loop, resulting in
n * 2 * log_2(n) + 3 * n
Then add 1 for the initialization of k, and n + 1 for the tests of the outer while condition, so the final T is
n * 2 * log_2(n) + 3 * n + 2
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论