算法基础#

查找算法#

二分查找#

最简单的查找算法, 面对有序列表, 每次从列表中间查找, 最多需要 $log_2{n}$ 次查找即可完成, 而简单查找至多需要 $n$ 步

示例(C):

1
int binarySearch(int *arr, int len, int target) {
2
  int low = 0;
3
  int high = len - 1;
4

5
  while (low <= high) {
6
    int mid = (low + high) / 2;
7
    int guess = arr[mid];
8
    if (guess == target) return mid;
9
    else if (guess > target) {
10
      high = mid - 1;
11
    }
12
    else {
13
      low = mid + 1;
14
    }
15
  }
16
  return -1;
17
}

示例(Python):

1
def binary_search(arr, item):
2
    low = 0
3
    high = len(arr) - 1
4

5
    while low <= high:
6
        mid = (low + high) // 2
7
        guess = arr[mid]
8
        if guess == item:
9
            return mid
10
        elif guess > item:
11
            high = mid - 1
12
        else:
13
            low = mid + 1
14

15
    return -1

排序算法#

冒泡排序#

最容易实现的排序算法, 原理是通过不断比较相邻元素大小, 将较小的元素提至列表前而将较大的元素提至列表后

时间复杂度:

最坏: $O(n^2)$ , 当整个列表逆序时
最好: $O(n)$ , 当列表已经有序时
平均: $O(n^2)$

空间复杂度:

$O(1)$ , 由于是原地排序算法, 不需要额外存储空间

示例(C):

1
void bubbleSort(int *arr, size_t len)
2
{
3
  int temp;
4
  for (int i = 0; i < len - 1; i++) {
5
    for (int j = 0; j < len - i - 1; j++) {
6
      if (arr[j] > arr[j + 1]) {
7
        temp = arr[j];
8
        arr[j] = arr[j + 1];
9
        arr[j + 1] = temp;
10
      }
11
    }
12
  }
13
}

示例(Python):

1
def bubble_sort(arr):
2
    for i in range(len(arr) - 1): #减不减1都可以
3
        for j in range(0, len(arr) - i - 1):
4
            if arr[j] > arr[j + 1]:
5
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
6

7
    return arr
8

9
def bubble_sort_optimized(arr): #更喜欢的写法, 列表有序时只需要遍历一次
10
    n = len(arr)
11
    flag = True
12
    while flag:
13
        flag = False
14
        for i in range(n - 1):
15
            if arr[i] > arr[i + 1]:
16
                flag = True
17
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
18
        n -= 1

选择排序#

原理是每次都从待排序数据中找到最小的元素并添加到已排序序列的末尾, 重复操作直至排序完成

时间复杂度:

无论输入数据是否有序, 都要进行 $\frac{n(n-1)}{2}$ 次操作, 固定为 $O(n^2)$

空间复杂度:

$O(1)$ , 由于是原地排序算法, 不需要额外存储空间

示例(C):

1
void selectionSort(int *arr, int len) {
2
  int temp;
3
  for (int i = 0; i < len; i++) {
4
    int min_idx = i;
5
    for (int j = i + 1; j < len; j++) {
6
      if (arr[j] < arr[min_idx]) {
7
        min_idx = j;
8
      }
9
    }
10
    temp = arr[i];
11
    arr[i] = arr[min_idx];
12
    arr[min_idx] = temp;
13
  }
14
}

示例(Python):

1
def selection_sort(arr):
2
    for i in range(len(arr)):
3
        min_idx = i
4
        for j in range(i + 1, len(arr)):
5
            if arr[j] < arr[min_idx]:
6
                min_idx = j
7
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
8

9
    return arr

快速排序#

原理是使用分治法Divide and Conquer的思想, 从列表中选取一个基准元素pivot, 将列表分为两部分: 一部分小于基准元素, 一部分大于基准元素. 然后递归对这两部分进行排序.

时间复杂度:

最坏: $O(n^2)$ , 当列表几乎有序时
最好: $O(n\log n)$
平均: $O(n\log n)$

空间复杂度:

由于采用了递归, 快速排序会占用栈空间, 最差情况下为 $O(n)$ , 最好情况下为 $O(\log n)$

示例(Python):

1
def quick_sort(arr):
2
    if len(arr) < 2: #基线条件
3
        return arr
4
    else: #递归条件
5
        pivot = arr[0]
6
        left = [x for x in arr[1:] if x < pivot]
7
        mid = [x for x in arr if x == pivot]
8
        right = [x for x in arr[1:] if x > pivot]
9
        return quick_sort(left) + mid + quick_sort(right)

数据结构#

数组和链表#

数组在内存中是连续的, 因此需要提前申请固定大小的内存空间, 而链表在内存中往往是不连续的, 因此对于单向链表来说每个节点都要存储下一个节点的地址, 而双向链表则需要存储节点前后两个节点的地址.

数组随机访问速度快, 而链表不能随机访问, 必须从第一个节点开始访问
数组插入和删除效率低, 内存固定, 而链表插入和删除效率高, 使用动态内存, 利用率高
读取复杂度: $O(1)$ 数组; $O(n)$ 链表
插入/删除复杂度: $O(n)$ 数组; $O(1)$ 链表

递归#

递归原理是函数调用自身, 实现相应目的. 一般来说每个递归函数都有基线条件和递归条件. 递归条件给出了进入递归的条件, 基线条件则用来限制函数无限递归.

使用示例(C):

1
int Fibonacci(int n) {
2
  if (n < 2) return n; //基线条件
3
  else return Fibonacci(n - 1) + Fibonacci(n - 2); //递归条件
4
}

使用示例(Python):

1
def fibonacci(n):
2
    if n < 2: #基线条件
3
        return n
4
    else: #递归条件
5
        return fibonacci(n - 1) + fibonacci(n - 2)

使用递归能有效解决很多问题, 但由于其反复进行堆栈操作, 某些时候会占用很大内存. 此时便可以考虑将递归结构改写成循环结构.