数値の平方根を計算するための（ひどい）アルゴリズムに遭遇しました。時間の複雑さについての小さな議論に入りました。私は時間の複雑さはO（n^2）であると主張します。なぜなら、n個の入力に対してn回乗算されるからです。私の友人は、時間の複雑さは実際にはO（n）であると主張する。誰が正当で、なぜですか？数値の平方根を計算するためのこの特定の（悪い）アルゴリズムの漸近的な複雑さは何ですか？
def squareRoot(x):
if x<0:
return "undefined"
elif x==0:
return 0
for i in range(0,x):
if(i*i)==x:
return i
最悪の場合、あなたはXの乗算とテストを実行し、ので、それは、O（n）のだ、ので、あなたの計算時間は、あなたの入力して線形に成長します。
ありがとうございます。私は今それを見る。 – hrazzer
まず、整数の乗算の複雑さを知る必要があります。
簡略化のため、Schönhage–Strassen algorithmを使用します。 n桁の数字の場合、複雑さはO(n log n log log n)です。もちろん
数n実際にそう乗算するn個のサイズまでのn個の数字がそう全体的に、それはO(n log n log log n log log log n)
O(log n log log n log log log n)
ある値nの数を乗算し、O(log n)数字を持っています
したがってO(n^2)はより正確で、同じ方法でO(n!)が正しいとしました。正解だが役に立たない。 O(n)は、間違っています。
さらに優れた乗算アルゴリズムを使用するとより効果的です。
このアルゴーの仕組みを見てみましょう。
最悪の場合、つまりxが完全な正方形ではなく、xが素数である場合、時間の複雑さはO（n）になります。
最高の場合です。それはnoです。完璧な正方形であれば、それはSQRT（n）の順になります。
あなたの主張に「n」とは何ですか？通常はアルゴリズムで処理される要素の数ですが、ここではそうではありません。 –