アルゴリズム時間複雑度

多くのプログラマーが、長い間プログラミングをしていたのに、アルゴリズムの時間の複雑さの推定が分からなかったのは悲しいことです.はっきりしないので、自分が書いたコードが効率的かどうかを深く考えず、最適化することで、コンピュータをより迅速かつ効率的にすることができるのではないでしょうか.だから私は最近アルゴリズムの時間の複雑さを独学で読んだ後、私は文章を書いて振り返り、記憶を深め、理解を助けることにしました.
アルゴリズム設計の要件
良いアルゴリズムの設計要件は、正確性、可読性、丈夫性、時間効率が高く、記憶量が低いという4つの特性に合致しなければならない.その中でアルゴリズムの最初の3つの特性は結局理解しやすいので、今日はアルゴリズムの時間効率という性質に重点を置いて整理します.
時間効率が高いとは,同じ問題に対して複数のアルゴリズムが解決でき,実行時間が短いアルゴリズムの方が効率が高く,実行時間が長いアルゴリズムの効率が低いことを意味する.生活の中で、人々はすべて最も少ないお金を使うことを望んで、最も短い时間、最大のことをして、アルゴリズムも同じ考えです.例えば、1つのクラスの物理平均点を求めることと全省の学生の中考物理平均点を求めることは、同じアルゴリズムで確かに問題を解決することができるが、占有時間とメモリの差は非常に大きいので、効率的で、低記憶空間のアルゴリズムを追求して問題を解決する必要がある.
アルゴリズム効率のメトリックメソッド
一般的に私たちはアルゴリズムの効率を分析し、有事後統計法と事前分析法を分析しますが、事後統計法には明らかに大きな欠陥があります.まず、プログラムを作成しなければなりません.これは通常、大きな時間と精力がかかります.だから一般的に私たちはアルゴリズムの分析に対して、事前に分析する必要があります.
高度なプログラム言語で作成されたプログラムは、コンピュータ上で実行する際に消費される時間は、次の要因に依存することがわかります.

アルゴリズムが採用するポリシー、方法

コンパイル生成コード品質

問題の入力規模

機器の実行指令の速度

第1条はもちろん1つのアルゴリズムの良し悪しを決定する根本であり、第2条はソフトウェアによって決定され、第4条は主にハードウェアの性能、すなわち、コンピュータソフトウェア、ハードウェアに関する要素を捨てて、1つのプログラムの実行時間は、アルゴリズムの良し悪しと問題の入力規模に依存する.入力規模とは、入力量の多少を指す.
だから私たちはアルゴリズムの問題を分析する時、最も重要なのはプログラムをプログラム設計言語から独立したアルゴリズムあるいは一連のステップと見なすことです.
関数の漸近成長

       ：      f(n) g(n),
        N，       n>N，f(n)   g(n) ,
      f(n)       g(n)。

1つのアルゴリズムの効率を判断する際,関数中の定数や他の副次的な項はしばしば無視できるが,主項(最高次数)の次数に注目すべきである.
一つのアルゴリズムが良いかどうかを判断するには、少量のデータでは結論が出ない.いくつかの関数の重要な実行回数における関数の漸近成長性を比較すると,あるアルゴリズムはnが大きくなるにつれて,他のアルゴリズムよりもますます優れ,あるいはもとは別のアルゴリズムよりも悪くなると解析できる.これは実は事前推定方法の理論的根拠であり,アルゴリズム時間の複雑さによってアルゴリズム時間効率を推定する.
アルゴリズム時間複雑度

        ，        T(n)       n   ，
    T(n)  n        T(n)    。
        ，          ，  ：T(n)=O(f(n))。
        n   ，           f(n)      ，
          ，        。
  f(n)     n     。

このように大きなO()を書くことで時間の複雑さを表す記法を大O記法と呼ぶ.
明らかに時間複雑度の定義から,アルゴリズムの時間複雑度はそれぞれO(1),O(n),O(n)であることが分かった.²),それらを非公式の名称で呼び,O(1)定数次,O(n)線形次,O(n)²)平方階、もちろん他にもいくつかの階があります.

//  O(1)   
sum = (1 + n) / 2 ;

//  O(n)   
    for (int i = 0; i < n; i++) {
        x++;
    }

//  O(n²)   

        for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                       x++;
        }
   }

大きいO階の方法を導く

   O ：

1、   1              。
2、            ，       。
3、           1，            。
        O 。

実は大きいO階の導き出しを理解するのは難しくなくて、得がたいのは数列のいくつかの関連演算に対して、ここでもっと多くの考察の数学の知識と能力で、特に数列の方面の知識と解題の能力です.
一般的な時間の複雑さ
実行回数関数
ステップ
非公式用語
12
O(1)
ていすうステップ
2n+3
O(n)
線形次数
3n²+2n+1
O(n²)
平方階
5log2n+20
O(logn)
たいすうかい
2n+3nlog2n+19
O(nlogn)
nlogn次数
6n³+2n²+3n+4
O(n³)
りっぽうだん
2^n
O(2^n)
インデックス次数
一般的な時間の複雑さに費やされる時間は、次のようになります.

O(1)

一般的に,特に説明がない場合,アルゴリズムの最悪の状況における時間的複雑さを解析した.
アルゴリズムの効率を分析することで、愚公の精神を深く感じることができるのは当然だが、ブルドーザーや爆薬はもっと現実的で賢いかもしれない.
簡単なアルゴリズムの時間複雑度の概念はまずここで終わり、後で新しい知識を見てから共有し続けます.