数据结构与算法1
第一个重要理论：操作的速度，并不按时间计算，而是按步数计算。
因为，你不可能很绝对地说，某项操作要花5秒。它在某台机器上要跑5秒，但换到一台旧一点的机器，可能就要多于5秒，而换到一台未来的超级计算机，运行时间又将显著缩短。所以，受硬件影响的计时方法，非常不可靠。
然而，若按步数来算，则确切得多。如果A操作要5步，B操作要500步，那么我们可以很肯定地说，无论是在什么样的硬件上对比，A都快过B。因此，衡量步数是分析速度的关键。
此外，操作的速度，也常被称为时间复杂度。在本书中，我们会提到速度、时间复杂度、效率、性能，但它们其实指的都是步数。
一般数据结构有4种操作：
- 读取 --- 查看数据结构中某一位置(索引)上的数据。
- 查找 --- 从数据结构中找出某个数据值的所在。
- 插入 --- 给数据结构增加一个数据值。
- 删除 --- 给数据结构增加一个数据值。
数据结构
数组
数组是计算机科学中最基本的数据结构之一。是一整块内存地址连续的区域。
- 读取，这只要一步就够了，因为计算机本身就有跳到任一索引位置的能力。
- 查找，线性查找，一个N格的数组，其线性查找的最多步数是N（N可以是任何自然数）。
- 插入，一个含有N个元素的数组，其插入数据的最坏情况会花费N + 1步。即插入在数组开头，导致N次移动，加上一次插入。
- 删除，对于含有N个元素的数组，删除操作最多需要N步。
集合
不允许元素重复的数据结构。
集合的读取跟数组的读取完全一样，计算机只要一步就能获取指定索引上的值。如之前解释的那样，这是因为计算机知道集合开头的内存地址，所以能够一步跳到集合的任意索引。
集合的查找也跟数组的查找无异，需要N步去检查某个值在不在集合当中。删除也是，总共需要N步去删除和左移填空。
但插入就不同了。先看看在集合末尾的插入。对于数组来说，末尾插入是最高效的，它只需要1步。
而对于集合，计算机得先确定要插入的值不存在于其中——因为这就是集合：不允许重复值。于是每次插入都要先来一次查找。
换句话说，在N个元素的集合中进行插入的最好情况需要N + 1步——N步去确认被插入的值不在集合中，加上最后插入的1步。
最坏的情况则是在集合的开头插入，这时计算机得检查N个格子以保证集合不包含那个值，然后用N步来把所有值右移，最后再用1步来插入新值。总共2N + 1步。
有序数组
有序数组跟上一章讨论的数组几乎一样，唯一区别就是有序数组要求其值总是保持有序。
import bisect
class OrderedArray:
def __init__(self):
self.data = []
def insert(self, value):
bisect.insort(self.data, value)
def __str__(self):
return str(self.data)
def __iter__(self):
return iter(self.data)
def __len__(self):
return len(self.data)
def __getitem__(self, index):
return self.data[index]
# 线性查找，时间复杂度为 O(n)
def linear_search(array, value):
for item in array:
if item == value:
return value
elif item > value:
break
return None
# 二分查找，时间复杂度为 O(log n)
def binary_search(array, value):
# 首先，设定下界和上界，以限定所查之值可能出现的区域
# 在开始时，以数组的第一个元素为下界，以最后一个元素为上界
lower_bound = 0
upper_bound = len(array) - 1
# 循环检查上界和下界之间的最中间的元素
while lower_bound <= upper_bound:
# 找出最中间位置的索引(使用整除运算符)
midpoint = (upper_bound + lower_bound) // 2
# 获取该索引的值
value_at_midpoint = array[midpoint]
if value < value_at_midpoint:
upper_bound = midpoint - 1
elif value > value_at_midpoint:
lower_bound = midpoint + 1
else:
return value_at_midpoint
# 当下界超越上界，数组中没有我们要找的值
return None
# 冒泡排序，时间复杂度为 O(n²)
def bubble_sort(array):
unsorted_until_index = len(array) - 1
is_sorted = False
while not is_sorted:
is_sorted = True
for i in range(unsorted_until_index):
if array[i] > array[i + 1]:
is_sorted = False
array[i], array[i + 1] = array[i + 1], array[i]
unsorted_until_index = unsorted_until_index - 1
# 嵌套循环，时间复杂度为 O(n²)
def has_duplicate_value(array):
for i in range(len(array)):
for j in range(len(array)):
if i != j and array[i] == array[j]:
return True
return False
def main():
array = [65, 55, 45, 35, 25, 15, 10]
bubble_sort(array)
print(array)
# oa = OrderedArray()
# oa.insert(10)
# oa.insert(5)
# oa.insert(1)
# oa.insert(7)
# oa.insert(20)
# oa.insert(11)
# oa.insert(2)
# oa.insert(15)
# oa.insert(3)
# oa.insert(9)
#
# print(oa)
#
# print(linear_search(oa, 3))
#
# print(binary_search(oa, 8))
if __name__ == "__main__":
main()
有序数组相比常规数组的一大优势就是它除了可以用线性查找，还可以用二分查找。常规数组因为无序，所以不可能运用二分查找。
排序
排序(Sorting)被认为是数据结构与算法中的基础。因为它在优化许多计算问题的效率、性能和简洁性方面发挥着关键作用。例如，二分搜索相较于线性搜索，速度快得多，但是要求数据已经排序。
Time complexity of binary search is O(log n), compared to O(n) for linear search.
许多高级算法依赖于有序输入才能实现最佳性能：
- 贪心算法 Greedy algorithms
- 分而治之策略 Divide and conquer strategies
- 动态规划 Dynamic programming
某些数据结构依赖于保持排序顺序
- 二叉搜索树 Binary Search Trees
- 堆 Heaps
- B 树 B-Trees
- 跳表 Skip Lists
冒泡排序
def bubble_sort(array):
if len(array) <= 1:
return
unsorted_until_index = len(array) - 1
is_sorted = False
while not is_sorted:
is_sorted = True
for i in range(unsorted_until_index):
if array[i] > array[i + 1]:
is_sorted = False
array[i], array[i + 1] = array[i + 1], array[i]
unsorted_until_index = unsorted_until_index - 1冒泡排序的时间复杂度是 O(n²)，规范一些来说：用 O(n²) 算法来处理 n 个元素，大约需要 n² 步。
O(n²) 也被叫作二次时间。
选择排序
def selection_sort(array):
if len(array) <= 1:
return
if not isinstance(array, list) or len(array) <= 1:
return array
for i in range(len(array)):
lowest_number_index = i
for j in range(i + 1, len(array)):
if array[j] < array[lowest_number_index]:
lowest_number_index = j
if lowest_number_index != i:
array[i], array[lowest_number_index] = array[lowest_number_index], array[i]
return array 选择排序的时间复杂度是 O(n²/2)，但是大 O 记法的一条重要原则是忽略常数，所以严格来说，选择排序的时间复杂度也是 O(n²)，类似的 O(2n) 也是 O(n)，O(100n)也是 O(n)。
因此，大 O 记法非常适合用于不同大 O 分类下的算法的对比，对于大O同类的算法，我们还需要进一步的解析才能分辨出具体差异。
插入排序
def insertion_sort(array):
if len(array) <= 1:
return
for index in range(1, len(array)):
position = index
temp = array[index]
while position > 0 and array[position - 1] > temp:
array[position] = array[position - 1]
position = position - 1
array[position] = temp插入排序的时间复杂度是 O(n²+2n-2)，但是大 O 有另一条重要规则大 O 只保留最高阶的N。所以在最坏的情况里，插入排序的时间复杂度跟冒泡排序、选择排序一样，都是 O(n²)。
散列表
大多数编程语言都自带散列表这种能够快速读取的数据结构。但在不同的语言中，它有不同的名字，除了散列表，还有散列、映射、散列映射、字典、关联数组。在 Python 中叫字典 dict，在 Java 中叫 HashMap 。
散列表里读取数据只需要 O(1)，因为其过程所花的时间是恒定的。它总是先计算出键的散列值，然后根据散列值跳到对应的格子去。
现在总算理解为什么我们的快餐店菜单用散列表会比用数组要快了。当要查询某种食物的价格时，如果是用数组，那么就得一个格子一个格子地去找，直至找到为止。无序数组需要O(N)，有序数组需要O(log N)。但用散列表的话，我们就能够以食物作为键来做O(1)的查找。这就是散列表的好处。
高效的软件离不开散列表，因为其O(1)的读取和插入带来了无与伦比的性能优势。
栈和队列
栈和队列并不是全新的东西，只不过是多加了一些约束条件的数组而已。但正是这些约束条件为它们赋予了巧妙的用法。
之前的散列表本质上也是存储在数组上，所以才能获得 O(1) 的读取和插入性能。
具体一点说，栈和队列都是处理临时数据的灵活工具。在操作系统、打印任务、数据遍历等各种需要临时容器才能构造出美妙算法的场景，它们都大有作为。
栈
栈存储数据的方式跟数组一样，都是将元素排成一行。但是它有以下3个约束条件
- 只能在末尾插入数据
- 只能读取末尾的数据
- 只能移除末尾的数据
栈很少用于需要长期保留数据的场景，却常用于各种处理临时数据的算法。
队列
队列对于临时数据的处理也十分有趣，它跟栈一样都是有约束条件的数组。它也有3个约束条件
- 只能在末尾插入数据
- 只能读取开头的数据
- 只能移除开头的数据
递归
和之前的排序一样，递归也是其他高级算法的基础。几乎所有循环都能够转换成递归。但能用不代表该用。
循环可能会造成死循环，同意递归也会。所以需要添加条件来结束递归。不再递归的情形称为基准情形。
from pathlib import Path
def get_dir(path):
path = Path(path) # 如果输入 string 则转成 Path 对象，如果输入是 Path 则不变
for item in path.iterdir():
if item.is_dir():
print(item.name)
get_dir(item)
def main():
get_dir("./")
if __name__ == "__main__":
main()采用递归来输出当前目录下的子目录及其子目录。正如打印所有目录的示例，递归十分适用于那些无法预估计算深度的问题。
需要注意的是将循环改成递归不会改变算法的大 O
之前介绍了一些排序算法，包括冒泡排序、选择排序和插入排序。但在现实中，数组排序不是通过它们来做的。为了免去大家重复编写排序算法的烦恼，大多数编程语言都自带用于数组排序的函数，其中很多采用的都是快速排序。其原理就是使用递归来给算法提速。
快速排序
快速排序是一种分治(divide-and-conquer)算法，依赖于一个名为分区的概念。
分区
此处的分区指的是从数组随机选取一个值，以其为轴(pivot)，将比它小的值放到它左边，比它大的值放到它右边。
假设有下面这样的数组
从技术上来说，选任意值为轴都可以，我们就以数组最右的值为轴吧。现在轴就是3了，我们把它圈起来。
然后放置指针，它们应该分别指向排除轴元素的数组最左和最右的元素。
接着就可以分区了，步骤如下：
1) 左指针逐个格子向右移动，当遇到大于或等于轴的值时，就停下来。
2) 右指针逐个格子向左移动，当遇到小于或等于轴的值时，就停下来。
3) 将两指针所指的值交换位置。
4) 重复上述步骤，直至两指针重合，或左指针移到右指针的右边。
5) 将轴与左指针所指的值交换位置。
当分区完成时，在轴左侧的那些值肯定比轴要小，在轴右侧的那些值肯定比轴要大。因此，轴的位置也就确定了，虽然其他值的位置还没有完全确定。
快速排序的效率
用大 O 记法来表达的话，它是 O(N log N)算法。
虽然快速排序在最好情况和最坏情况都没能超越插入排序，但在最常遇见的平均情况，前者的 O(N log N) 比后者的 O(N^2) 好得多，所以总体来说，快速排序优于插入排序。
以下是各种时间复杂度的对比：
由于快速排序在平均情况下表现优异，于是很多编程语言自带的排序函数都采用它来实现。因此一般你不需要自己写快速排序。但你可能需要学会写快速选择——它是一种类似快速排序的实用算法。
代码
def original_partition(array):
low = 0 # 左指针在数组最开始
pivot_index = len(array) - 1 # 轴在数组最后一位
pivot = array[pivot_index]
high = len(array) - 2 # 右指针在除轴后最后一位
# 当指针重合，或左指针移到右指针的右边时停止
while True:
# 移动左指针
while array[low] < pivot:
low = low + 1
# 移动右指针
while array[high] > pivot:
high = high - 1
if low >= high:
break
else:
# 将两指针所指的值交换位置
temp = array[low]
array[low] = array[high]
array[high] = temp
# 将轴和左指针的值交换
array[pivot_index] = array[low]
array[low] = pivot
print(array)
def partition(array, low, high):
pivot_index = high
pivot = array[pivot_index]
high = high - 1
while True:
# 移动左指针
while low <= high and array[low] < pivot:
low = low + 1
# 移动右指针
while low <= high and array[high] > pivot:
high = high - 1
# 当指针重合，或左指针移到右指针的右边时停止
if low >= high:
break
else:
# 将两指针所指的值交换位置
array[low], array[high] = array[high], array[low]
# 将轴和左指针的值交换
array[pivot_index], array[low] = array[low], pivot
# 返回轴的位置
return low
def quicksort(array, low, high):
if low >= high:
return
pivot = partition(array, low, high)
quicksort(array, low, pivot - 1)
quicksort(array, pivot + 1, high)
if __name__ == "__main__":
array = [0, 5, 2, 1, 6, 3, 4]
quicksort(array, 0, len(array) - 1)
print(array)快速选择
假设有一个无序的数组，你不需要将它排序，只要找出里面第10小的值，或第5大的值。就像从一堆测试成绩中找出第25百分位，或找出中等成绩那样。
你首先想到的，可能是把整个数组排序，然后再跳到对应的格子里去找。
但这样做的话，即使是用快速排序那样高效的算法，一般也需要O(N log N)。虽然这也不算差，但一种名为快速选择的算法可以做得更好。快速选择需要对数组分区，这跟快速排序类似，或者你可以把它想象成是快速排序和二分查找的结合。
def partition(array, low, high):
pivot_index = high
pivot = array[pivot_index]
high = high - 1
while True:
# Move left pointer past elements <= pivot
while low <= high and array[low] <= pivot:
low = low + 1
# Move right pointer past elements >= pivot
while low <= high and array[high] >= pivot:
high = high - 1
if low >= high:
break
else:
array[low], array[high] = array[high], array[low]
# Swap pivot with final position
array[pivot_index], array[low] = array[low], pivot
return low
def quick_select(array, index, low, high):
if low >= high:
return array[low]
pivot = partition(array, low, high)
if index < pivot:
return quick_select(array, index, low, pivot - 1)
elif index> pivot:
return quick_select(array, index, pivot + 1, high)
else:
return array[pivot]
if __name__ == "__main__":
array = [0, 5, 2, 1, 6, 3]
value = quick_select(array, 2, 0, len(array) - 1)
print(value)本笔记由阅读《数据结构与算法图解》(杰伊 温格罗/袁志鹏译)而作
评论已关闭