どのようにアルゴリズムの成長率と時間量を計算するには？

Question

私は現在楽しんでいます複雑さを考えるアレン・ダウニーと数時間前に私は成長率のセクションを終了しました。私は読書やグーグルの成長率を一時停止し、その本が私に与えた情報を広げた。私はまた、時間を計算することができることを発見しました。アルゴリズムで生データを計算するのにかかる時間です。私はGoogleによって答えられない多くの質問を持っている、または多分私が理解するのに役立つので、私は私の答えに個人的なタッチが必要です。私の質問は：

1-単純なアルゴリズムの成長率をどのように計算することができますか？例えば、私はちょうどテイラーシリーズを使用してラジアンで指定した角度のサインを計算し、このループを書いた：

for i in range(0, 360): 
     return sum(((-1)**i/(factorial((2 * i) + 1))) * d ** ((2*i) + 1)) 

階乗：

def factorial(n): 
    factorial = 1 
    for i in range(1, n+1): 
     factorial *= i 

return factorial 

は、どのように私はその成長率を計算していますか？

私はBogosortのような非常に悪いアルゴリズムに精通しました。 bogosortを使用して配列をソートするには、大量の時間がかかります。しかし、あなたはどのように時間を計算していますか？それはコンピュータによって異なります。

3- Big-O表記法とはどのようなもので、成長率とはどのような関係がありますか？

ご回答ありがとうございます。

Answer 1

一般に、関数が多くの要因に依存するため、関数の時間を計算するのは良いアプローチではありません。この理由のために、私たちはしばしば計算ステップの点で複雑さを表現します。

複数の表記が存在します（大きなオメガ、大きなオメガ、ビッグセータ）。 Big-Ohは上限を表します。したがって、O（n）は、最悪の場合、n個のステップを実行することを示します。

Big-Omega（Ω）は下限であるため、Ω（n）は最小nステップを示します。 両方の組み合わせがbig-thetaӨであるため、Ө（n）は正確にn桁を取ることを示します。あなたのケースで

は、factorialは、この関数は意志ループがN + 1回に1から

def factorial(n): 
    factorial = 1 
    for i in range(1, n+1): 
     factorial *= i 

return factorial 

として定義され、したがって、その引数nに依存します。正確にn個のステップを実行すると言うことができるので、factorialがӨ（n）にあると言うことができます。これは明らかに線形であることに注意してください。