[解決済み] 私の関数の時間的複雑さはどのくらいですか？重複

質問

複雑さについて勉強を始めたが、これには苦労している。

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) で、2回目は O(n/2) ... そして、そのような log(n) を何度も繰り返すのでしょうか？ ということは O(n) * O(log(n)) = O(n * log(n)) complexity . これで良かったのでしょうか？

編集：（重複しないように）ビッグ・オーが何であるかは知っています。具体的な事例で正しい評価を聞いてきました。

どのように解決するのですか？

外側のループは 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)) であり、期待通りです。