全部解けたらレッドコーダー！？ #計算量解析クイズＨＡＲＤ

たとえば、N=1024 の場合、計算回数は、 10*1 + 9*1 + 8*2 + 7*4 + 6*8 + 5*16 + 4*32 + ... + 1*512 となり、ほとんどの i に対して j のループが 1 回であることが分かります。 実際に、計算回数は定数部分まで見積もると 2N に収束します。（N が大きい場合）

再帰関数を用いた問題になりますが、計算回数はフィボナッチ数列の第 N 項に比例します。したがって、計算量は O(1.618...^N) になります。なお、1.618... の値は「黄金数」と呼ばれています。

i が決まった時の j, k ループ内の計算量は O((N/i)log(N/i)) なので、全体の計算回数は O((N/1)log(N/1) + (N/2)log(N/2) + ... + (N/N)log(N/N)) であることが分かります。 そこで、N/x log (N/x) を 1 から N にかけて積分した値は (Nlog^2 N)/2 なので、答えは O(Nlog^2 N) です。

合計計算回数は、N/sqrt(1) + N/sqrt(2) + ... + N/sqrt(N) であることが分かります。これは x を用いて N/sqrt(x) を 1 から N までの区間で積分した値に近くなります。 1/sqrt(x) の積分は sqrt(x) * 定数になるので、求める値は N*sqrt(N)*定数=O(N^1.5) になります。

たとえば、N に 18 を入力しましょう。そうすると、18 は (9, 10) に分かれます。(9, 10) は (4, 5, 6) に分かれます。(4, 5, 6) は (2, 3, 4) に分かれます。…　そのように、各階層につき最大で 3 つしか出現しません。したがって、計算量は 3 * logN = O(logN) です。

2 進数の bit ごとに考えると、ある桁について「i のループで選ばれるか」「j のループで選ばれるか」「k のループで選ばれるか」「l のループで選ばれるか」「どれでも選ばれずに最後まで残るか」の 5 通りがあるので、計算量は O(5^N) です。

最大公約数が 1 でない確率は、最大公約数が 2の倍数, 3の倍数, 4の倍数, ..., Nの倍数、となる確率を考えて、1/4 + 1/9 + 1/16 + ... + 1/(N^2) = 0.6449... 以下になります。したがって、最大公約数が 1 である確率は 1-0.6449...=0.3551 以上になり、Nによらず定数時間であることが分かります。

これはマージソートです。マージソートの計算量は O(NlogN) なので、答えは O(NlogN) です。

各 x に対して、計算回数は 2^sqrt(x) になります。これを 1 から N に対して積分すると、O(2^sqrt(N) × sqrt(N)) のオーダーになるのです！！！

計算量は、O(N^(log(7)/log(4))) = O(N^1.4036...) となります。これは多倍長演算の一つのアルゴリズムである「Toom-Cook-4 法」を単純化したものです。詳しい話はこちらの記事をお読みください。（https://qiita.com/square1001/items/1aa12e04934b6e749962）