資料結構和算法入門

定義

資料結構就是指一組資料的存儲結構，算法就是操作這組資料的一組方法。

學習方法

資料結構和算法不用死記，我們要學習它的“來曆”“自身的特點”“适合解決的問題”以及“實際的應用場景”，盡量手寫實作。

複雜度分析

資料結構和算法本身解決的是“快”和“省”的問題，即如何讓代碼運作得更快，如何讓代碼更省存儲空間。是以時間和空間就是衡量一個算法執行效率的總要名額。

時間複雜度

int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }      

這段代碼的時間T(n)=2+2n，這裡的低階、常量、系數都不會左右代碼執行時間的增長趨勢，是以可以直接忽略，即這段代碼的時間複雜度為O(n)。

大 O 時間複雜度實際上并不具體表示代碼真正的執行時間，而是表示代碼執行時間随資料規模增長的變化趨勢，是以，也叫作漸進時間複雜度（asymptotic time complexity），簡稱時間複雜度。

時間複雜度分析

1. 隻關注循環執行次數最多的一段代碼

1. 加法法則：總複雜度等于量級最大的那段代碼的複雜度

1. 乘法法則：嵌套代碼的複雜度等于嵌套内外代碼複雜度的乘積

幾種常見的時間複雜度

O(1)、O()、O(n)、O()、O()、O()…

1. O(1)

   隻要算法中不存在循環語句、遞歸語句，即使有成千上萬行的代碼，其時間複雜度也是Ο(1)。

2. O()、O()

int i=1;
 while (i <= n)  {
   i = i * 2;
 }      

這段代碼的執行次數為x，=n，x=，如果代碼裡面2變為3，則推倒公式為:

=n，x==。

在采用大 O 标記複雜度的時候，可以忽略系數，即時間複雜度都為。

最好、最壞、平均時間複雜度

// n表示數組array的長度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}      

這段代碼是在一個數組中找到元素x的位置，找到過後結束。

這裡最好和最壞分别是X元素第一個位置和在最後一個位置，即O(1)和O(n)。這裡極端情況發生機率不是很大，是以我們需要計算平均時間複雜度。

要查找的變量 x 在數組中的位置，有 n+1 種情況：在數組中和不在數組中。我們把每種情況下，查找需要周遊的元素個數累加起來，然後再除以 n+1，就可以得到需要周遊的元素個數的平均值，即：

​​

​1+2+3+……+n+n/n+1 = n(n+3)/2(n+1)​

​，即時間複雜度為O(n)

空間複雜度

表示算法的存儲空間與資料規模之間的增長關系。

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }
}