Java-時間の複雑さと空間の複雑さ

1、アルゴリズム効率
アルゴリズム効率解析は2つに分けられる:1つ目は時間効率であり,2つ目は空間効率である.時間効率を時間複雑度と呼び,空間効率を空間複雑度と呼ぶ.時間複雑度は主にアルゴリズムの実行速度を測定し、空間複雑度は主にアルゴリズムに必要な余分な空間を測定し、コンピュータの発展の初期にはコンピュータの記憶容量が小さい.だから空間の複雑さを気にしています.しかし、コンピュータ業界の急速な発展を経て、コンピュータの記憶容量はすでに高いレベルに達している.アルゴリズムの空間的複雑さに特に注目する必要はありません
2、時間複雑度
2.1時間複雑度の概念
時間複雑度の定義:コンピュータ科学では、アルゴリズムの時間複雑度は関数であり、アルゴリズムの実行時間を定量的に記述する.一つのアルゴリズムの実行にかかる時間は、理論的には計算できません.あなたのプログラムを機械の上に置いて走ってこそ、知ることができます.しかし、アルゴリズムごとにテストする必要がありますか?すべてのテストができますが、これは面倒なので、時間の複雑さという分析方法があります.1つのアルゴリズムにかかる時間は、文の実行回数に比例し、アルゴリズムにおける基本操作の実行回数は、アルゴリズムの時間複雑度である.
2.2大Oの漸進表現

//      func1          ？
void func1(int N){
     
int count = 0;
for (int i = 0; i < N ; i++) {
     
   for (int j = 0; j < N ; j++) {
     
       count++;
   }
}
for (int k = 0; k < 2 * N ; k++) {
     
 count++; }
int M = 10;
 while ((M--) > 0) {
     
 count++; }
 System.out.println(count);
}

Func 1が実行する基本操作回数:

						             F（N）=N*N + 2*N + 10  

実際に時間の複雑さを計算する場合,正確な実行回数を計算する必要はなく,おおよその実行回数しか必要としないが,ここでは大きなOの漸進表現を用いる.
大きいO記号(Big O notation):関数の漸進的な挙動を記述するための数値記号
運転時間中のすべての加算定数を定数1で置換する大きなO次法を導いた.2.修正後の実行回数関数では、最上位項目のみ保持します.3、最上位の項目が存在して1でない場合、この項目に乗じた定数を除去します.得られた結果は大きなO次であった.大Oのプログレッシブ表現を用いた後,Func 1の時間的複雑度は次のようになる.

                                        O(N2)       N2=N*N

2.3一般的な時間複雑度の計算例
例1:

//   bubbleSort      
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;
   }
}}

例2:

//   binarySearch      
int binarySearch(int[] array, int value) {
     
int begin = 0;
int end = array.length - 1;
while (begin <= end) {
     
   int mid = begin + ((end-begin) / 2);
   if (array[mid] < value)
       begin = mid + 1;
   else if (array[mid] > value)
       end = mid - 1;
   else
       return mid; }
return -1; }

例3:

//       factorial      
long factorial(int N) {
     
 return N < 2 ? N : factorial(N-1) * N; }

例4:

//         fibonacci      
int fibonacci(int N) {
     
 return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

インスタンス分析:
例1基本動作はN回,最悪実行(N*(N−1))/2回であり,大O次法+時間的複雑度を導くことにより一般的に最悪,時間的複雑度はO(N^2)である.
実施例2基本動作は、最良1回、最悪O(logn)回、時間的複雑度O(logn)ps:lognがアルゴリズム解析において底数2、対数Nと表される.lgNと書くところもあります.(二分検索は毎回半分の不適合値を排除するので、一次二分残り:n/2二次二分残り:n/2/2=n/4)
例3計算解析により,基本動作はN回再帰され,時間的複雑度はO(N)であることが分かった.
例4計算解析により,基本動作は2 N回再帰され,時間的複雑度はO(2 N)であることが分かった.
3、空間複雑度
空間複雑度は、実行中にアルゴリズムが一時的に記憶空間のサイズを占有するメトリックです.空間複雑度はプログラムがどれだけbytesを占有しているかではなく、これもあまり意味がないので、空間複雑度は変数の個数を計算します.空間複雑度計算規則は基本的に実践複雑度と類似しており,大きなO漸進表現も用いられる.
例1:

//   bubbleSort      
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; 
 } 
 } 
}

例2:

//   fibonacci      
int[] fibonacci(int n) {
      
 long[] fibArray = new long[n + 1]; 
 fibArray[0] = 0; 
 fibArray[1] = 1; 
 for (int i = 2; i <= n ; i++) {
      
 fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; 
 } 
 return fibArray; 
}

例3:

//       Factorial      
long factorial(int N) {
      
 return N < 2 ? N : factorial(N-1)*N; 
}

インスタンス分析:

例1は定数個の余分な空間を用いたので,空間複雑度はO(1)

であった.

例2はN個の空間を動的に開き、空間複雑度はO(N)

である.

インスタンス3は、N回再帰的に呼び出され、N個のスタックフレームが開かれ、各スタックフレームは定数個の空間を使用する.空間的複雑度はO(N)である.