これを数式にする方法がわかりません。
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j += i) {
何が起こるかを理解しています。i++ごとに、jの1レベル少ない乗算があります。
i = 1 の場合、j = 1、2、3、...、100 となります。
i = 2 の場合、j = 1、3、5、...、100 となります。
これをビッグシータの観点からどのように考えればよいかわかりません。
j の合計は N、N/2、N/3、N/4...、N/N (私の結論)
これを N の関数として考えるにはどうすればよいでしょうか?
したがって、あなたの質問は実際には「調和級数 1/1 + 1/2 + 1/3 + ... + 1/N のタイトな境界は何ですか?」に減らすことができます。答えはどれlog Nですか（離散ではなく連続和と見なすことができ、の積分は であることに注意して1/Nくださいlog N）
あなたのハーモニックシリーズは、アルゴリズム全体の公式です（あなたが正しく結論付けたように）
だから、あなたの合計：
N + N/2 + N/3 + ... + N/N = N * (1 + 1/2 + 1/3 + ... + 1/N) = Theta(N * log N)
したがって、アルゴリズムのタイト バウンドは次のようになります。N*log N
[厳密な] 数学的証明はこちら(「積分検定」と「発散率」の部分を参照)