アルゴリズムの基本原理

一、時間複雑度:(1)定数時間の操作:一つの操作がデータ量と関係がなければ、毎回一定時間内に完成する操作を定数操作と呼ぶ.(2)時間複雑度はアルゴリズムフローにおける定数動作数の指標である.O(big Oと読む)で表されることが多い.具体的には、定数動作数の式では、高次項、低次項、高次項の係数が不要であれば、残りの部分をf(N)と記すと、時間複雑度はO(f(N))となる.(3)アルゴリズムフローの良し悪しを評価し,時間複雑度の指標を見てから,異なるデータサンプルでの実際の実行時間,すなわち定数項時間を解析する.時間の複雑さを簡単に理解する例:1つの秩序配列A、もう1つの無秩序配列B、Bの中のすべてのAにない数を印刷してください.A配列の長さはNで、B配列の長さはMです.アルゴリズムフロー1:配列Bの各数について、Aの中で遍歴する方式で探します;時間複雑度は:O(M * N)アルゴリズムフロー2:配列Bの各数について、Aの中で2分の方法で探します;時間複雑度は:O(M * logN)二分検索の時間複雑度は:O(logN)アルゴリズムフロー3:まず配列Bを並べ替えて、それから類似の外列の方式ですべてAの中で現れた数を印刷します;先に並べ替えます:O(M∗log2M)O(M∗log2M)比較:O(N+M)O(N+M)だから時間の複雑度は:O(M∗log2M)+O(N+M)なら得ることができます:A数の組長、B配列が短いならば、アルゴリズム3はもっと良くて、この時Nがもっと大きいためです;A配列が短い場合、B数組長の場合、アルゴリズム2は、このときNが小さいため、Mが大きい2、空間複雑度:空間複雑度(Space Complexity)は、1つのアルゴリズムが実行中に一時的に記憶空間の大きさを占有するメトリックであり、S(n)=O(f(n))と記載され、nは問題の規模である.アルゴリズムの空間的複雑さを利用して,アルゴリズムの実行に必要なメモリ空間を予め推定することができる.1つのアルゴリズムの実行には、自身が使用する命令、定数、変数、入力データのほかに、データを操作する作業ユニットと計算に必要な補助空間が必要です.アルゴリズムの実行に必要な記憶領域には、次の2つの部分があります.(1)固定部分.この空間の大きさは、入出力されるデータの個数、数値とは無関係である.主に命令空間(すなわちコード空間)、データ空間(定数、単純変数)などが占める空間を含む.この部分は静的空間に属する.(2)動的に割り当てられた空間や、再帰スタックに必要な空間などを主に含む可変空間.この部分の空間サイズはアルゴリズムに関係している.三、安定性:ソートアルゴリズムの安定性は、一般的には、ソート前の2つの等しい数がシーケンスの前後位置順序とソート後の2つの前後位置順序と同じであることを保証することができる.簡単な形式化では、Ai=Aj、Aiが元の位置の前にある場合、ソート後のAiはAjの位置の前にある必要があります.
ソートアルゴリズム
へいきんじかんふくざつさ
さいさじかんふくざつさ
くうかんふくざつさ
データオブジェクトの安定性
バブルソート
O(n2)
O(n2)
O(1)
あんてい
ソートの選択
O(n2)
O(n2)
O(1)
配列不安定、チェーンテーブル安定
ソートの挿入
O(n2)
O(n2)
O(1)
あんてい
クイックソート
O(n*log2n)
O(n2)
O(log2n)
ふあんてい
ヒープのソート
O(n*log2n)
O(n*log2n)
O(1)
ふあんてい
集計ソート
O(n*log2n)
O(n*log2n)
O(n)
あんてい
ヒルソート
O(n*log2n)
O(n2)
O(1)
ふあんてい
カウントソート
O(n+m)
O(n+m)
O(n+m)
あんてい
バケツソート
O(n)
O(n)
O(m)
あんてい
ベースソート
O(k*n)
O(n2)
あんてい
1つのアルゴリズムでは,その時間的複雑さと空間的複雑さは往々にして相互に影響する.より良い時間的複雑さを追求すると、空間的複雑さの性能が悪くなる可能性があります.すなわち、より多くの記憶領域を占有する可能性があります.逆に、より良い空間複雑度を求めると、時間複雑度の性能が悪くなる可能性があります.すなわち、実行時間が長くなる可能性があります.また,アルゴリズムのすべての性能の間には多かれ少なかれ相互影響が存在する.したがって,アルゴリズム(特に大型アルゴリズム)を設計する際には,アルゴリズムの各性能,アルゴリズムの使用頻度,アルゴリズムが処理するデータ量の大きさ,アルゴリズム記述言語の特性,アルゴリズムが動作する機械システム環境などの各要素を総合的に考慮して,比較的良いアルゴリズムを設計することができる.