[解決済み] 複雑さ O(log(n)) は O(sqrt(n)) と同等か？

質問

私の教授は、入力の長さを半分にする演算は、経験則としてO(log(n))の計算量になると教えてくれたところです。なぜO(sqrt(n))ではないのでしょうか、どちらも等価ではないのでしょうか？

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

等価ではありません。 sqrt(N) よりもずっと早く増加します。 ログ <サブ 2 (N) . 定数は存在しない C を持つことになります。 sqrt(N) < C.log(N) のすべての値に対して N ある最小値より大きい。

これを簡単につかむには、次のようになります。 ログ <サブ 2 (N) の（2進数の）桁数に近い値になります。 N 一方 sqrt(N) の半分の桁数を持つ数となります。 N があります。あるいは、それを等式で表すと

ログ <サブ 2 (N) = 2log <サブ 2 (sqrt(N))

の対数(!)を取る必要があるわけです。 sqrt(N) と同じオーダーの複雑さにするために ログ <サブ 2 (N) .

例えば、11桁の2進数の場合、0b10000000000（=2 ¹⁰ ) の場合、平方根は0b100000ですが、対数は10にしかなりません。