なぜそれは、対数の底はアルゴリズムの時間複雑さを見つけるのに常に2と見なされますか？

Question

は、内側ループはO（N）回実行し、各時間iが（実際に保守的な上限として、これは確かに時間的に一部算出する仕事量N MOD行うことができないこと

function isPrime(n): 
for i from 2 to n - 1: 
    if (n mod i) = 0, return false 
return true 

、このコードを検討しますO（n^3））。したがって、この全体的なアルゴリズムは時間O（n^4）で実行され、場合によってはより高速に実行されます。

私たちのアルゴリズムは時間O（n^4）で実行されますが、それは入力ビット数の関数として何ですか？まあ、数nを書き出すには、O（log n）ビットが必要です。したがって、入力nを書き出すのに必要なビット数をxとすると、このアルゴリズムの実行時間は実際にはO（2 ^（4x））であり、xの多項式ではありません。ここ

私の質問は

は番号を書き込むには、Nビットで、それはnビットを記録（ベース10）を取る必要があります。したがって、xをビット数とすると、実際の実行時間はO（10 ^（4x））でなければなりません。これはO（2 ^（4x））とは大きく異なります。どのようにしてこのような近似をすることができますか？あなたが任意に大きな数字（ひいてはBIGNUMライブラリ）を使用していない限り

Answer 1

対数ベース間の変換は、ある定数で乗算することと等価です。定数の乗算は大きなOの複雑さのクラスに影響しません。したがって、対数ベースは解析に影響を与えません。

しかし、あなたの質問の例は実際に対数ではありません。これは指数表現のように、逆のものです。しかし、この例を正確に理解することはできません。なぜなら、「ログnビット（ベース10）を取らなければなりません」というフレーズは私には意味がないからです。あなたが主張するように、数字nは実際にはlog n (base 2)ビットを持ち、ベース10はありません。

Answer 2

は、整数レジスタに収まるとのビット「上」の数にかかわらずを実行するのに一定の時間を要するCPU命令によって直接的に詳述されています入力。したがって、内部ループのモジュロ演算はO（1）です。

一方、nがの場合、実際にはに境界がありますが、もちろんmodがO（1）であるとは言えません。

アルゴリズムが数字の桁数で多項式であると想像したとしても、あなたが選択するベースは実際には問題ありません：modはO（d^a）です。dは小数はnである（すなわち、d = log10（n））。異なる基底の対数は、単に乗法因子によって異なるので、log10（n）= klog2（n）となるので、O（log10（n））^ a）= O（k^a（log2（n））^ big-oh表記法は乗法定数には興味がないので、実際には同じであることがわかりますので、a = O（（log2（n））^ a）です。各命令のためにあなたが正確にマシンサイクルの数を言うことができるシンプルなCPUを、上で完全に本当

---

1. 。現代のCPUは複雑であり、個々の命令のコストは決定するのがより複雑ですが、通常は入力の正確なビットパターンに依存しません。

Answer 3

あなたの関数は、nのbase-2表現か、base-10表現のどちらかをとります。最初のケースでは、入力サイズは明白にx = log_2(n)であり、後者では入力可能なサイズはx = log_10(n)です。アルゴリズムがn^4（たとえば）に比例する時間がかかる場合、最初のマシンはO((2^x)^4 = O(2^(4x))、後者はO((10^x)^4) = O(10^(4x))となります。実際、10^(4x)は容易に確認できるように2^(4x)より遥かに速く漸進的に成長する。

マシンモデルが特定の解析で一定に保たれていると想定されるため、通常これは問題とは見なされません。マシンモデルを変更すると複雑さについて多くのことが変わる可能性があることを示すのは簡単です。例えば、パリンドロームを検出することは、RAMマシンでは線形時間、単一テープ決定論的チューリングマシンでは二次時間をとることが知られている。

さらに重要なことは、特定のモデル内の整合性です。そして、あなたが与えられたモデル（マシンはバイナリまたは小数です）の中にとどまっている限り、心配はありません。

「待ってください」と言うと、「私は1台のマシン上に置くことができ、バイナリまたは小数点として入力を符号化する文字列を渡すことができます！これは本当です。しかし、この場合、基数2の表現を取り、O（n）を必要とするアルゴリズムは、O（n）を取る小数のものと比較して実際にはより速い（入力の関数として）。どうして？ nはそれぞれの場合の入力サイズの指数関数であり、2は10より小さな基底であるからです。したがって、この場合有用な情報を示します（しかしここでは対数は取っていません。

実際には、関数の実行時間の分析に関係するので、対数を指数と混同しています。対数の基底は互換性がありますが、指数の基底はそうではありません。