時間の複雑さと空間の複雑さの計算

2854 ワード

一、アルゴリズムの時間複雑度定義
一般的に、アルゴリズムで基本的な動作を繰り返し実行する回数は問題規模nの関数であり、T(n)で表し、nが無限大に近い場合、T(n)／f(n)の極限値がゼロに等しくない定数である場合、f(n)はT(n)の同数関数である.T(n)＝O(f(n))と記し、O(f(n)と称する.アルゴリズムの漸進時間複雑度(Oは数量レベルの符号)であり、時間複雑度と略す.
1、定義に基づいて、基本的な計算手順(1.)をまとめて基本的な操作の最悪の場合実行回数T(n)を計算することができます.
(2)T(n)の桁を計算します.(数段を計算するには最高べき乗だけを保持し、係数を省略します.)f(n)＝T(n)で関数を表します.
(3)時間の複雑さを大きなOで表し、O(係数を省略する最高乗)で表します.
一般的な時間複雑度:O(1)例:

//hash     
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
//hash       
 tab[i = (n - 1) & hash

hashmapチェーンの位置を取得するT(n)=2サイクルの時間複雑度はO(1)です.

   public static void main(String[] args) {
        //      
        int[] numbers=new int[]{1,5,8,2,3,9,4};
        int i,j;
        for(i=0;inumbers[j+1])  
                {
                    int temp=numbers[j];  //n*n  (      )
                    numbers[j]=numbers[j+1];  //n*n  (      )
                    numbers[j+1]=temp;  //n*n  (      )
                }
            }
        }
        System.out.println("           :");
        for(i=0;i

発泡体の並べ替えの複雑さは、T(n)=n^2+n^2+n^2で、上の括弧の同数級によって、n^2がT(n)の同数級であることが確認できます.
f(n)=n^2があり、T(n)/f(n)によって限界を求めると定数cが得られます.
このアルゴリズムの時間複雑度:T(n)=O(n^2)

//   a（           ）   x，     
//low    a    ，high     
//             ，     -1
    public static int binary_search(int[] a,int low,int high,int value){
    if(low>high) return -1;
    int mid=low+((high-low)>>1);
    if(a[mid]==value){
        return mid;
    }else if (a[mid]

二分割法の計算方法は、配列の中の点を取り続け、中間点との比が必要と判断し、適当な半分を選択します.最悪の場合は配列の境界値を取ります.この時、2^T(n)=n T(n)=log 2^n(n)=log 2^n、ループの時間複雑度はO(logn)です.
二、アルゴリズムの空間複雑度定義アルゴリズムの空間複雑度は計算アルゴリズムに必要な記憶空間によって実現され、アルゴリズムの空間複雑度の計算式は、S(n)＝O(f(n))と記載されています.ここで、nは問題の規模であり、f(n)は文がnの記憶空間に対する関数であり、「漸進表現法」でもあります.「固定空間メモリ」(基本プログラムコード、定数、変数などを含む)と「変動空間メモリ」(プログラム実行時にサイズが変わる使用空間)
計算方法:再帰的アルゴリズムの空間複雑度=再帰的深さN*が再帰的に必要な補助空間は、単スレッドにとって再帰的に実行時スタックがあり、再帰的に最も深いあのスタックによって消費される空間の個数が求められている.再帰的に最も深い空間は、再帰的にすべての再帰的プロセスを収容するのに十分である.
前に計算時間の複雑さを書いたとき、再帰的な二分法について書きました.再帰的にすべての変数に対して一回の割当を行いました.時間の複雑さを分析します.nを計算するとlog 2^n回の計算が必要になりますので、同じlog 2 nの割当値を行います.空間複雑度はlog 2 nです.

  public static int binary_search(int[] a,int n,int x){
    int low=0;
    int high=n-1;
    while(low<=high){
        int mid=low+((high-low)>>1);
        if(a[mid]>x){
            high=mid-1;
        }else if (a[mid]

これはサイクル実現に関する二分法ですが、基本ステップではデータ変数値を作成しますので、空間複雑度はO(1)です.

アルゴリズムの正確性証明方法1:サイクル不変量

[シリーズ記事]データ構造とアルゴリズムのゲッターアップ(一)