データ構造01-時間複雑度と空間複雑度

1:アルゴリズムの複雑度
1.1:データ構造とアルゴリズム定義

データ構造(data structure):挿入、削除、検索、更新、エルゴードなどのデータを管理するためのプログラム構造であり、よく見られるデータ構造は配列、チェーン、キュー、スタック、ツリー、HASHなどである.

アルゴリズム(algorithm):問題を解決する方法とその実現を指す.アルゴリズムは、基本演算および所定の演算順序からなる完全な解題ステップとして理解できる.例えば、各種の並べ替え方法、折半検索などが一般的なアルゴリズムです.

アルゴリズムの良し悪しの判断基準:

時間複雑度

空間複雑度

1.2:時間複雑度

時間の複雑さ:アルゴリズムを実行するために必要な計算作業量.

文の頻度(時間頻度):1つのアルゴリズムのステートメントの実行回数をステートメントの頻度または時間の頻度と呼び、T(n)と表記し、nは問題の規模である.

一つのアルゴリズムが費やす時間は、アルゴリズム中のステートメントの実行回数に比例します.どのアルゴリズムの中でステートメントが実行回数が多く、時間がかかりますか?
一般的に、アルゴリズムで基本的な動作を繰り返し実行する回数は、問題規模nのある関数である.T(n)=4 n 2+5 n、または8 n 2+1のように、時間の複雑さは、O(n^2)となり、最高べき乗をとり、係数を除去します.
一般的な時間複雑度は、定数次数O(1)、対数次数O(logn)、線形次数O(n)、線形対数次数O(nlogn)、平方次数O(n 2)、立方次数O(n 3)、…、k次数O(nk)、指数次数O(2 n)である.問題の規模nが増加するにつれて、上記時間の複雑さは増加しつつあり、アルゴリズムの実行効率は低下する.つまり効率的に見ると、彼らの優劣は以下の通りです.
O(1)＞O(logn)＞O(n 2)＞O(n 3)＞O(2 n)
時間の複雑さを計算する時、まずアルゴリズムの基本的な操作を見つけて、それぞれの語句に基づいてその実行回数を決めて、T(n)の同数級(その同数級は以下があります.時間複雑度T(n)=O(f(n))
時間複雑度計算の一般的な方法は、
何重のforサイクルがあるかを見てください.重さだけでは時間の複雑さはO(n)、二重はO(n^2)となります.このようにして、二分があればO(logn)、二分が例えばクイックソート、二分検索、もし一つのfor循環が一つの二分ならば、時間の複雑さはO(nlogn)です.

//1.             ：
int max(int x, int y) {
       return x>y?x:y;
}
         ：x>y?x:y。      。  ，        O(1)

//2.               ：
for (i=1;i<=n;++i) {
    for (j=1;j<=n;++j) {
        c[i][j]=0;     //              ：n   
        
        for (k=1;k<=n;++k)  
           c[i][j] += a[i][k]*b[k][j]; //              ：n    
    }
}
//  ，T(n)=n^3+n^2；          ，      ，        ：O(n^3)

//3.              O(n^2)
void bubblesort(int a[], int n) {
       int i, j, tmp;

       for (i = 0; i < n-1; i++) {
              for (j = n-1; j >= i+1; j--) {
                     if (a[j] < a[j-1]) {
                            tmp = a[j];
                            a[j] = a[j-1];
                            a[j-1] = tmp;
                     }
              }
       }
}

1.3:空間複雑度
空間複雑度:アルゴリズムが消費するメモリ空間を指す.
その計算と表現方法は時間複雑さと類似しており、複雑さの漸近性で一般的に表現されている.時間の複雑さに比べて、空間の複雑さの分析はずっと簡単です.プログラムは、動作時に動的に割り当てられた空間や、再帰的なスタックに必要な空間などです.この部分の空間サイズはアルゴリズムと関連している.これらの静的な空間、例えばコード、定数、および簡単な変数は空間複雑度に無関係である.

//       1   2：
//  1：
void reversestr(char *str, int len) {
       for(int i = 0; i < len/2;i++) {
              char tmp;

              tmp = str[i];
              str[i] = str[len-i-1];
              str[len-i-1] = tmp;
       }
}
//  1      ，          tmp，          O(1)。

//  2：
char *reversestr(char *str, int len) {
       char *strnew = (char *)malloc(len+1);

       if (strnew == NULL) {
              return NULL;
       }

       memset(strnew, 0, len+1);
       int pos = 0;

       for(int i = len-1; i >=0; i--) {
              strnew[pos++]= str[i];
       }

       return strnew;
}
//  2       ，         ，                  ，            O(n)。

//        ：          ，       0 65536  。
#define MAXMUM 65536

void FindRepeated(int a[], int n) {
       int tmp[MAXMUM];//        ，      a[]        
       int i;
       
       for (i = 0; i < MAXMUM; i++) {
              tmp[i] = 0;
       }

       for (i = 0; i < n; i ++) {
              tmp[a[i]]++;//  a[]    ， tmp[]     ， 1
      }

       for (i = 0; i < MAXMUM; i++) {
              if (tmp[i]>1)//  tmp[i]    1，  i    a[]     
              printf(“%d”, i);

       }

}

  ，               ？   ：O(1)。        ，        tmp[MAXMUM]        ，          ，              ，         O（1）。