質問が「ばかげている」場合はご容赦ください。私はアルゴリズムの時間の複雑さに慣れていません。
n個の数値があり、それらを合計したい場合、「nステップ」かかることを理解しています。つまり、アルゴリズムはO(n)または線形時間です。つまり、実行されるステップ数は、入力数 n に比例して増加します。
この合計を 5 回ずつ行う新しいアルゴリズムを作成すると、O(5n) = O(n) 時間であり、線形であることがわかります ( wikipediaによると)。
質問
10個の異なるO（n）時間アルゴリズム（合計、線形時間ソートなど）があるとします。そして、n個の入力でそれらを次々と実行します。
これは、全体としてこれが O(10n) = O(n)、線形時間で実行されることを意味しますか?
はい、任意の定数kに対してO(kn)、 = O(n)
問題が大きくなり始めて、10 個の線形演算が実際には k 個の線形演算に基づいていると判断した場合、たとえば、k がユーザー入力配列の長さであると判断した場合、ビッグオーからその情報を削除するのは正しくありません。
big-O の定義から作業を進め、それが正しいことを「証明」したら経験則を学ぶのが最善です。
10 個のアルゴリズムがある場合、それは 10 個のO(n)定数 C 1から C 10があることを意味し、各アルゴリズム A iの実行にかかる時間は、十分に大きな n に対してC i * n よりも短くなります。
したがって、[*] 十分に大きな n に対して 10 個のアルゴリズムすべてを実行するのにかかる時間は、次の時間よりも短くなります。
C 1 * n + C 2 * n + ... + C 10 * n
= (C 1 + C 2 + ... + C 10 ) * n
したがって、合計もO(n)、一定の C 1 + ... + C 10です。
経験則: 一定数のO(f(n))関数の合計は ですO(f(n))。
[*] この証拠は読者に残されています。ヒント: 考慮すべき「十分」の値は 10 通りあります。
はい、O(10n) = O(n) です。また、O(C*n) = O(n)、ここで C は定数です。この場合、C は 10 です。C が n に等しい場合、O(n^2) のように見えるかもしれませんが、そうではありません。C は定数なので、n によって変化しません。
また、複雑さの合計では、最高位または最も複雑なものが全体的な複雑さと見なされることに注意してください。この場合、O(n) + O(n) ... + O(n) の 10 回です。したがって、それは O(n) です。