gpt4 book ai didi

algorithm - 时间复杂度分析。选择运算符来计算一行代码运行的次数

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:24:08 24 4
gpt4 key购买 nike

分析此伪代码的时间复杂度。右边是我对每行运行次数的看法。我不确定是使用 log n 、 n log n 还是简单地 n 用于 while 循环..请帮忙

                                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

因此:O(n log n)

这是正确的吗?

最佳答案

如果你的 while 循环是:

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)

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

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

关于algorithm - 时间复杂度分析。选择运算符来计算一行代码运行的次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21501407/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com