c - 我的函数的时间复杂度是多少？

<分区>

开始研究复杂性，我正在努力解决这个问题:

void what(int n) {
    int i;
    for (i = 1; i <= n; i++) {
        int x = n;
        while (x > 0)
            x -= i;
    }
}

好吧，第一个 for 循环显然是 O(n)。第一次迭代是 O(n)，第二次是 O(n/2).. 这样 log(n) 次我猜测？这意味着 O(n) * O(log(n)) = O(n * log(n)) 复杂度。我做对了吗？

编辑:(不是重复的)我知道 Big O 是什么。我问过具体案例的正确评价。

最佳答案

外循环运行 n 次。

对于每次迭代，内部循环运行 n/i 次。

总运行次数为:

n + n/2 + n/3 + ... + n/n

渐近地(忽略整数算术舍入)，这简化为

n * (1 + 1/2 + 1/3 + ... + 1/n)

这个系列松散地收敛于 n * log(n)。

因此，如您所料，复杂度为 O(N.log(N))。

关于c - 我的函数的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35326140/

相关文章：

algorithm - 内容相关搜索:对购物产品进行分类