今日、msdnでブログに出くわし、アルゴリズムの時間計算量を計算する方法に気づきました。アルゴリズムの時間計算量を計算する方法を完全に理解していますが、最後に著者は以下の行に言及しました
私が得るすべてを合計する
（N + 4）+（5N + 2）+（4N + 2）= 10N + 8
したがって、上記のコードの漸近時間計算量はO（N）です。これは、上記のアルゴリズムがライナー時間計算量アルゴリズムであることを意味します。
それで、なぜ著者はそれがライナー時間計算量アルゴリズムに基づいていると言われるのですか？ブログへのリンク
彼は、10N+8は一次方程式だからだと言った。その方程式をプロットすると、直線が得られます。10 * x + 8このWebサイト（関数グラフ）に入力してみて、自分の目で確かめてください。
著者は、最も適切なものを選択した経験に基づいています。アルゴリズムの複雑さを数えることは、ほとんどの場合、Big-Oh関数を見つけることを意味します。これは、与えられた関数（この場合は10N + 8 ）の上限にすぎません。
よく知られている複雑さのタイプは、線形複雑さ、2次複雑さなどです。したがって、時間計算量をカウントする最後のステップは、与えられた関数に使用できる複雑度の低いタイプ（つまり、線形は2次式よりも複雑度が低く、 2次式は指数関数よりも複雑度が低いなど）を選択することです。 、その複雑さを正しく説明しています。
あなたの場合、O（n）とO（n ^ 2）、さらにはO（2 ^ n）も正解です。しかし、 Big-Oh表記の定義に完全に適合する、それほど複雑でない関数はO（n）であり、これがここでの答えです。
これは本当に良い記事であり、 Big-Oh表記について完全に説明されています。
時間計算量の昇順（一般的なもの）
O(1) - Constant
O(log n) - logarithmic
O(n) - linear
O(n log n) - loglinear
O(n^2) - quadratic
注：Nは際限なく増加します
複雑さの理論については、確かにいくつかの背景理論を読む必要があります。これは通常、漸近的な複雑さに関するものです。そのため、小さな部分を削除して、複雑さのクラスのみを保持することができます。
重要なアイデアは、との違いが一度無視できるようになることNは本当に大きいということです。N+5N
詳細については、こちらをお読みください。
非常に実用的なルールは次のとおりです。
アルゴリズムsiの複雑さが次のようなポリで表される場合、複雑さA*n^2+B*n+C の次数 （つまり、O（何か））は変数nの最高次数に等しくなります。
ポリではA*n^2+B*n+C、順序はO（n ^ 2）です。
josnidhinが説明したように、ポリが