我的函数的时间复杂度是多少？ [英] What is the time complexity of my function?

问题描述

开始研究复杂性，我为此感到困惑：

Started studying about complexity, I'm struggling with this one:

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）。 code> log（n）次？
表示 O（n）* O（log（n））= O（n * log（n））复杂度 。我正确了吗？

Well, the first for loop is clearly O(n). The first iteration is O(n), second one is O(n/2).. and like that log(n) times I guess? Which means O(n) * O(log(n)) = O(n * log(n)) complexity. Did I get this right?

编辑：（不是重复的）我知道Big O是什么。我已经要求在特定情况下进行正确的评估。

(not a duplicate) I know what Big O is. I've asked the correct evaluation in a specific case.

推荐答案

外部循环运行 n 次。

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

For each iteration, the inner loops runs n / i times.

运行总数为：

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

渐近（忽略整数算术舍入），简化为

Asymptotically (ignoring integer arithmetic rounding), this simplifies as

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

该系列大致收敛于 n * log（n）。

因此，复杂度为 O（N.log（N））。

这篇关于我的函数的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！