数学结构与算法

[MatNoble]

数据结构是计算机存储、组织数据的方式。
算法是一系列规定的计算步骤，为了实现特定的计算目的。

程序 = 数据结构 + 算法

数据结构: 程序用来储存数据的基本单位
       算法: 为了实现特定目的，一系列操作数据的方式
==>
一个程序把数据存储在特定的数据结构中，并使用特定的算法进行数据的计算

数据结构和算法之间的关系密不可分:

• 特定算法有时候需要基于特定的数据结构，比如二分查找就要基于排好序的数组。
• 数据结构也往往集成了特定的算法，比如优先队列就集成了排序算法在其中。

[MatNoble]

二分搜索 Binary Search

在有序数组中查找特定元素

# while 循环
def binarySearch(List, left, right, target):
    while left <= right:
        mid = left + (right - left) // 2
        if List[mid] == target:
            return mid
        elif target < List[mid]:
            right = mid - 1
        elif target > List[mid]:
            left = mid + 1
    return -1
# 递归
def binarySearchR(List, left, right, target):
    if left > right:
        return -1
    mid = left + (right - left) // 2
    if target < List[mid]:
        right = mid - 1
        return binarySearchR(List, left, right, target)
    elif target > List[mid]:
        left = mid + 1
        return binarySearchR(List, left, right, target)
    return mid

时间复杂度

N = 2^k ==> k = logN

[MatNoble]

时间空间复杂度

时间空间复杂度 = 时间空间增长趋势

Big O Notation

大 O 表示法：算法的渐进时间复杂度
T(n) = O(f(n))

时间复杂度

符号	说明	举例
O(1)	常数阶	赋值，根据下表查找数组元素的值
O(logN)	对数阶	二分查找
O(n)	线性阶	Loop 顺序查找，双指针，滑动窗口
O(nlogN)	线性对数阶	快速排序，归并排序
O(n^2)	平方阶	插入排序，选择排序，冒泡排序
O(n^k)	k 次方阶	-
O(2^n)	指数阶	-
O(n!)	阶乘阶	-

空间复杂度

内存空间增长的趋势

符号	说明	举例
O(1)	常数阶	赋值
O(n)	线性阶	数组
O(n^2)	平方阶	矩阵

[MatNoble]

链表 LinkedList

链表

[MatNoble]

Tree 树

• 根节点 -- Root / Leaf
• Height / Depth
• Subtree
• Edge / Parent Node / Child Node / Left/Right Node

1. 排序二叉树(Binary Search Tree)：每个节点的数值比左子数上的每个节点都大，比所有右子树的节点都小
2. 红黑树(Red-Black Tree)：是一种自平衡二叉寻找树