データ構造とアルゴリズム学習の認識時間の複雑さ

認識時間の複雑さ
定数時間の操作:1つの操作がデータ量と関係がない場合、毎回一定時間以内に完了する操作であり、これを定数操作、例えば加減算乗数、配列のアドレス操作と呼ぶ.
時間複雑度はアルゴリズムフローにおける定数動作数の指標とする.O(big Oと読む)で表されることが多い.具体的には、定数動作数の式では、高次項、低次項、高次項の係数が不要であれば、残りの部分をf(N)と記すと、時間複雑度はO(f(N))となる.アルゴリズムフローの良し悪しを評価し,まず時間複雑度の指標を見てから,異なるデータサンプルの下での実際の運転時間,すなわち定数項時間を解析する.
余分な複雑な空間O(1)
アルゴリズムを完了すると、無秩序配列のソートのように、与えられた配列自体のメモリ空間を除いて、この配列のソートを完了するには、新しい配列を作成して今回のソートを完了する必要がある場合、新しい配列が占めるメモリ空間を追加複雑空間と呼び、新しい配列の長さがnのように、追加複雑空間をO(n)とします.
たいすうき
アルゴリズムを設計すると,そのアルゴリズムの正確性を正確に検証することはできないが,この場合,対数器という方法を用いることで,自分のアルゴリズムの正確性を検証するのに大きな効率を得ることができる.これは間違いなく私たちにとって大きな助けになります.対数器とは何ですか.
対数器の概念と使用
0、測りたい方法がありますa.1、絶対的に正しいが複雑度が悪い方法bを実現する.2、ランダムサンプル発生器を実現する.3、対比を実現する方法.4、方法aと方法bを何度も比較して、方法aが正しいかどうかを検証する.5.比較エラーが発生したサンプルがある場合、印刷サンプル分析はどの方法でエラーが発生したか.6、サンプル数が多い場合、テストは依然として正確であり、方法aが正しいと判断できる.
一般的なソート方法

バブルソート

public class Code_BubbleSort {
 
public static void bubbleSort(int [] arr) {
      for(int i=0;iarr[j]) {
                    swap(arr,j-1,j);
              }           
          }
      }
  }
public static void swap(int []arr,int i,int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

分析:バブルアルゴリズムはよく見られるソートアルゴリズムの一つであり、ソートは簡単で、時間の複雑度はO(n*n)であり、大量のデータセットに対してバブルソートアルゴリズムを採用することは提案されていない.

選択ソート選択ソートは、隣接する2つの要素を比較し、要素の最小の下付き文字を見つけてデータ交換を行う.

public class Code_SelectSort {

    public static void selectSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
      }
      for(int i=0;i

分析:時間の複雑さはO(n*n)であり、現在のアーキテクチャ設計やビジネスロジックの大部分で選択ソートアルゴリズムがあまり使われていない.

挿入ソート挿入ソートも一般的なソート方法であり、バブルソートと選択ソートに対して、ソート中にソート対象の要素を順番に選択してソートした要素と比較し、現在の要素と前の要素より小さい場合は指定した位置に挿入します.抽象的なソート方法

です

public class Code_InsertSort {

    public static void insertSort(int [] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        for(int i = 1;i=0 && arr[j] > arr[j+1] ;j--) {
              swap(arr, j, j+1);
          }
      }
    }
  public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

解析:時間的複雑度はO(n*n)であり,抽象的であるが,挿入ソートはデータソートを実現するビジネスロジックによく用いられる.
対数器を使用して、挿入ソートの正確性を検証します.

public class TestInsertSort {
    
    //    
    public static void rightMethod(int [] arr) {
          Arrays.sort(arr);
    }

  //        
   public static int [] generateRandomArray(int size, int value) {
        int [] arr = new int[(int)((size + 1) * Math.random())];
        for(int i=0; i=0 && arr[j] > arr[j+1] ;j--) {
                swap(arr, j, j+1);
            }
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
//           
  public static boolean isEquals(int []arr1, int []arr2) {
          if( (arr1 == null && arr2 !=null) || (arr1 != null && arr2 == null)) {
              return false;
         }
    }
      if(arr1 == null && arr2 == null) {
          return false;
      }
      if(arr1.length != arr2.length) {
          return false;
      }
     for(int i=0;i