算法学习一

发表于 | 分类于

最近写论文写不动，然后又不知道干点啥来荒废时间，正好看到了一本挺有意思的算法书《我的第一本算法书》，准备读一读，结合一些开源的程序，学习一下，并实现一下。本文的主要内容来自于《我的第一本算法书》和维基百科。

算法的时间复杂度

算法的时间复杂度通常用 $O$ 符号来表示，它的意思是忽略重要项以外的内容，比如说 $O(n^2)$ 表示算法的运行时间最长为 $n^2$ 的常数倍。

  1. 如果链表中的数据量为 $n$，我们从链表头部线性查找，如果目标在链表最后，需要的时间为 $o(n)$。链表中添加数据只需要更改两个指针的指向，所以耗费的时间与 $n$ 无关。如果到达了添加(删除)数据的位置，那么添加(删除)只需要 $O(1)$ 的时间。
  2. 数组与链表不同，数据是通过下表确定内存地址的，所以访问 $n$ 个数据的某个数据仅为恒定的 $O(1)$ 时间。若向数组中添加数据，则需要将目标位置的数据之后的数据一个个移开，如果在头部添加数据则需要 $O(n)$ 时间，删除同理。
  3. 在哈希表中，可以采用哈希函数快速访问到数组中的目标数据，如果发生哈希冲突，我们就使用链表进行存储。
  4. 在堆中，假设有 $n$ 个节点，根据堆的特点我们可以知道堆的高度为 $log_2\ n$ (类似于等比数列求和)，那么对堆进行排序时间复杂度为 $O(log\ n)$。
  5. 二叉搜索树的比较次数取决于树的高度，如果节点为 $n$，树的的形状又较为均衡的话，比较的大小和移动的次数最多为 $log_2\ n$， 因此时间复杂度为 $O(log\ n)$。

排序

所谓排序就是讲数据按照升序的方式调整顺寻，下面将介绍几种常见的排序算法。

冒泡排序

冒泡算法重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。冒泡排序对 $n$ 个数据的排序的时间复杂度 $O(n^2)$ 。

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
def bubble_sorted(iterable):
    new_list = list(iterable)
    list_len = len(new_list)
    for i in range(list_len - 1):
        for j in range(list_len - 1, i, -1):
            if new_list[j] < new_list[j - 1]:
                new_list[j], new_list[j - 1] = new_list[j - 1], new_list[j]
    return new_list
    
testlist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
print('sorted:', bubble_sorted(testlist))

选择排序

选择排序是一种简单直接的排序算法。它的工作原理如下：首先找到未排序列中最小的元素，存放在
排序序列的其实位置，然后再从剩余未排序元素中寻找最小元素，然后放到一排序序列的末尾，一次类推，知道所有元素排序完毕，如下图所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def selection_sort(arr):
    for i in range(len(arr)):
        minIndex=i
        for j in range(i+1,len(arr)):
            if arr[minIndex]>arr[j]:
                minIndex=j
        if i==minIndex:
            pass
        else:
            arr[i],arr[minIndex]=arr[minIndex],arr[i]
    return arr
if __name__ == '__main__':
    testlist = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12]
    print(selection_sort(testlist))

插入排序

插入排序的工作原理是通过构建有序序列，对于为排序数据，在一排序序列中从后向前扫描，找到相应位置并插入，如下图所示。算法的时间复杂度为 $O(n^2)$。

1
2
3
4
5
6
7
8
9
10
def insertion_sort(lst):
    n=len(lst)
    if n==1: return lst
    for i in range(1,n):
        for j in range(i,0,-1):
            if lst[j]<lst[j-1]: 
                lst[j],lst[j-1]=lst[j-1],lst[j]
            else:
                break
    return lst

堆排序

堆排序是指利用对这种数据结构设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于(或者大于)它的父节点。堆排序的顺序是将元素进行重排，以匹配堆的条件。下图中排序过程之前简单地绘出了堆树的结构。

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#!/usr/bin/env python
#-*-coding:utf-8-*-
def heap_sort(lst):
    def sift_down(start, end):
        """最大堆调整"""
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and lst[child] < lst[child + 1]:
                child += 1
            if lst[root] < lst[child]:
                lst[root], lst[child] = lst[child], lst[root]
                root = child
            else:
                break

# 创建最大堆

    for start in range((len(lst) - 2) // 2, -1, -1): ## 从最后一个子节点出开始进行最## 大堆调整
        sift_down(start, len(lst) - 1)

# 堆排序
    for end in range(len(lst) - 1, 0, -1):
        lst[0], lst[end] = lst[end], lst[0]
        sift_down(0, end - 1)
    return lst


def main():
    l = [9, 2, 1, 7, 6, 8, 5, 3, 4]
    print(heap_sort(l))

if __name__ == "__main__":
    main()

归并排序

归并排序会将序列分成长度相同的来那个子序列，当无法继续往下分时(也就是每个子序列只有一个数据时)，就对子序列归并。归并指的是把来那个排好序的子序列合并成一个有序序列。该操作会一直进行，知道所有子序列都归并为一个整体为止。归并排序的算法时间复杂度为 $O(nlog\ n)$。

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Recursively implementation of Merge Sort
def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result += right
    return result


def merge_sort(L):
    if len(L) <= 1:
        # When D&C to 1 element, just return it
        return L
    mid = len(L) // 2
    left = L[:mid]
    right = L[mid:]

    left = merge_sort(left)
    right = merge_sort(right)
    # conquer sub-problem recursively
    return merge(left, right)
    # return the answer of sub-problem
if __name__ == "__main__":
    test = [1, 4, 2, 3.6, -1, 0, 25, -34, 8, 9, 1, 0]
    print("original:", test)
    print("Sorted:", merge_sort(test))

快速排序

快速排序是在数列中挑选一个元素作为基准(pivot)，然后将数列按照“比基准小的数”和“比基准大的数”分为两类，然后进行使用快速排序进行递归排序“比基准小的数”和比“基准大的数”。快速排序的算法平均时间复杂度为 $O(nlog\ n)$，因为其内部循环可以再大部分框架上很有效率的完成，所以称之为快速算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    less = []
    greater = []
    pivot = lst.pop()
    for item in lst:
        if item < pivot:
            less.append(item)
        else:
            greater.append(item)
    lst.append(pivot)
    return quick_sort(less) + [pivot] + quick_sort(greater)

P问题，NP问题，NP Complete问题，NP困难问题

这部分是偶然看到的，和这里关系不大。
P问题是指在多项式时间内可以解决的问题；NP问题是指在多项式时间内可以判断的问题；NP Complete是指在多项式时间内判断，不能在多项式时间内解决的问题。NP困难问题是指如果所有的NP问题都可以在多项式时间内归约到某个问题。
具体上面问题的分布情况可以参照下面的图，目前普遍认为 $P \neq NP$，如果$P = NP$，那么这个世界确实会很不一样，人人都能成为莫扎特系列。

非常感谢各位老板投喂！