Java-時間の複雑さと空間の複雑さの総括!

アルゴリズム効率:1、時間効率時間効率は時間複雑度と呼ばれ、主に1つのアルゴリズムの運行速度2、空間効率空間効率は空間複雑度と呼ばれ、主に1つのアルゴリズムに必要な余分な空間はコンピュータの発展の初期に、コンピュータの記憶容量はとても小さいので、空間複雑度に対してとても気にしています.しかし、コンピュータ業界の急速な発展は、コンピュータのストレージ容量が大きくなったため、アルゴリズムの空間的複雑さに特に注目する必要はありません.時間複雑度:プログラム実行の効率は時間複雑度と空間複雑度であり、単純に時間で測定すると、ハードウェア構成が大きく異なる可能性があるため、ハードウェア条件の干渉を排除するために、単純にソフトウェアからプログラム実行の速さを記述し、時間複雑度を導入した.アルゴリズムにおける基本操作実行回数は,アルゴリズムの時間的複雑さである.(実際には時間の複雑さは正確ではなく、プログラムの実行効率の「桁数」しか推定できません)
O(N^2)は時間の複雑さを表す形式であり、時間の複雑さを計算する際には、必ずしも正確な実行回数を計算する必要はなく、おおよその実行回数だけを必要とし、大きなO記号(Big O notation)の漸進的な表現を用いる.時間の複雑さは主に1つのコードの中で基本的な操作が実行する回数の数量級を見ます:実行回数の数量級が小さいほど、現在のこのようなプログラムの実行速度が速いと思っています;実行回数の桁数が大きいほど、現在のようなプログラムの実行速度が遅いと考えられる.Nは問題の規模に相当する.O(1)よくある時間の複雑さは,問題の規模にかかわらず,基本操作回数は一定である(1は必ずしも1回実行するとは限らず,複数回でもよいが,問題の規模に関係なく定数であっても)O(N)O(M+N)は2つの変数で問題の規模O(N^2)バブルソート時間の複雑さ(暗記!!)を記述する.一般に時間的複雑度といえば、デフォルトでは最悪の場合の複雑度を指す.以下は7種類のソートアルゴリズムで、それぞれのソートの時間の複雑さ、コードはどのように書きますか(すべてしっかり覚えています!!)一般的な7種類のソートアルゴリズム(1.バブルソート、2.クイックソート、3.挿入ソート、4.ヒルソート、5.クイックソート、6.集計ソート、7.スタックソート)空間複雑度:空間複雑度:空間複雑度:1つのアルゴリズムが実行中に一時的に記憶空間を占有するサイズのみを測定する(入力データを除外する)空間複雑度はプログラムがどれだけbytesを占有しているかを測る空間ではないので、空間複雑度は変数の個数を計算し、数級の角度からプログラムの一時空間がどれだけ占有しているかを大まかに測り、空間複雑度計算規則は基本的に実際の複雑度と類似しており、大O漸進表現も使用されている.例:バブルソートの空間的複雑さを計算するには:

void bubbleSort(int[] array) {
 for(int end=array.length;end>0;end--) {
  boolean sorted=true;
  for(int i=1;i<end;i++) {
   if(array[i-1]>array[i]) {
    Swap(array,i-1,i);
    sorted=false;
   }
  }
  if(sorted===true) {
   break;
  }
 }
}

このアルゴリズムは常熟個の余分な記憶空間を用いているので,空間複雑度はO(1)である.