datetime:2023-06-03 15:30
author:nzb
认识复杂度和简单的排序算法
认识时间复杂度
常数时间的操作
一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
例如：列表取某一位的值就是常数操作，因为列表是一块连续的内存，可以通过偏移量取到，而链表取某一位值是，需要遍历下一个数据，它的内存不是连续的，而是用指针指向另一块内存
时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O(读作big O)来表示。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。
在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那么时间复杂度为O(f(N))。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”，也就是用实际跑一遍程序对比。
算法流程按照最差情况来估计时间复杂度
选择排序、冒泡排序细节的讲解与复杂度分析
时间复杂度O(N^2)
额外空间复杂度O(1)
选择排序
import random
data = list(range(20))
random.shuffle(data)
print(data)
# 额外空间，i、min_idx、j，有限数量，所以O(1)
for i in range(len(data)):
min_idx = i
for j in range(i + 1, len(data)):
if data[j] < data[min_idx]:
min_idx = j
data[i], data[min_idx] = data[min_idx], data[i]
print(data)
- 冒泡排序
import random
data = list(range(20))
random.shuffle(data)
print(data)
"""
5 7 6 2 4 1
第1次循环：5 6 2 4 7 0~N-1范围做比较，确定 N-1 位置的值，
第2次循环：5 2 4 6 7 0~N-2范围做比较，确定 N-2 位置的值，
第3次循环：5 2 4 6 7 0~N-3范围做比较，确定 N-3 位置的值，
第4次循环：2 4 5 6 7 0~N-4范围做比较，确定 N-4 位置的值，
第5次循环：2 4 5 6 7 0~N-5范围做比较，确定 N-5 位置的值，
等差数列：aN^2 + bN + c，留高阶项：O(N^2)
"""
# 额外空间，i、j，有限数量，所以O(1)
for i in range(1, len(data)): # 循环次数
for j in range(len(data) - i): # 循环索引
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
插入排序细节的讲解与复杂度分析
[3, 2, 5, 4, 2, 3, 1]- 下标
0~0：有序 - 下标
0~1：2比3少，则0和1位置交换，再往前看，没数了，则0~1有序了，即：[2, 3, 5, 4, 2, 3, 1] - 下标
0~2：5不比3小，则不看了0~2有序了，即：[2, 3, 5, 4, 2, 3, 1] - 下标
0~3：4比3小，4和3位置交换，再往前看，4不比3小，则不看了，0~3有序了，即：[2, 3, 4, 5, 2, 3, 1] - 下标
0~4：2比5小，2和5位置交换[2, 3, 4, 2, 5, 3, 1]，再往前看，2比4小，交换[2, 3, 2, 4, 5, 3, 1]，再往前看，2比3小，交换[2, 2, 3, 4, 5, 3, 1]，再往前看，2不比2小，则不看了，0~4有序了，即：[2, 2, 3, 4, 5, 3, 1] - 下标
0~5：3比5小，3和5位置交换[2, 2, 3, 4, 3, 5, 1]，再往前看，3比4小，交换[2, 2, 3, 3, 4, 5, 1]，再往前看，再往前看，3不比3小，则不看了，0~5有序了，即：[2, 2, 3, 3, 4, 5, 1] 下标
0~6：1一直会往前看，并交换，直到不比前面小或前面没数了，则0~6有序了，即：[1, 2, 2, 3, 3, 4, 5]总结：插入排序的时间复杂度跟数据状况的不同而不同
[7, 6, 5, 4, 3, 2, 1]：交换次数(等差数列)：1+2+3+4...，时间复杂度：O(N^2)[1, 2, 3, 4, 5, 6, 7]：每次看一下，不用交换，时间复杂度：O(N)- 推算一个算法的时间复杂度表现，都是按最差情况下的时间复杂度，及插入排序为：
O(N^2)
data = [3, 2, 5, 4, 2, 3, 1]
print(data)
for i in range(len(data)):
# for j in range(i - 1, -1, -1): # 包括 i-1，不包括 -1
for j in range(i)[::-1]: # 包括0，不包括 i
if data[j] > data[j + 1]: # j+1 == i
data[j], data[j + 1] = data[j + 1], data[j]
else:
break
print(data)
二分法的详解与扩展
- 1）在一个有序数组中，找某个数是否存在，时间复杂度，
O(logN)，logN以二为底，即log2^N的缩写
比如17个数，需要对半到8个数，然后再对半到4个数，然后再对半到2个数，再对半到1个数，总共砍4次，即
log2^16=4比如8个数，需要对半到4个数，然后再对半到2个数，再对半到1个数，总共砍3次，即log2^8=3比如4个数，需要对半到2个数，再对半到1个数，总共砍2次，即log2^4=2
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
def bin_search(d, search_data):
start, end = 0, len(d) - 1
while start <= end:
# mid = (start + end) // 2
# >> 1也可以写成 // 2, 为什么不用上面那个，因为 start + end 可能内存溢出，而 end 和 start 不会溢出，end - start 也不会
mid = start + ((end - start) >> 1)
# print(start, end, mid, data[mid])
if d[mid] > search_data:
end = mid - 1
elif d[mid] < search_data:
start = mid + 1
else:
return mid
return -1
print(bin_search(data, 5))
- 2）在一个有序数组中，找
>=某个数最左侧的位置
# ix = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
data = [1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6]
def bin_search(d, search_data):
start, end = 0, len(d) - 1
idx = -1
while start <= end:
# mid = (start + end) // 2
# >> 1也可以写成 // 2, 为什么不用上面那个，因为 start + end 可能内存溢出，而 end 和 start 不会溢出，end - start 也不会
mid = start + ((end - start) >> 1)
# print(start, end, mid, data[mid])
if d[mid] >= search_data:
idx = mid
end = mid - 1
else:
start = mid + 1
return idx
print(bin_search(data, 3))
- 3）局部最小值问题(使用二分法查找，不一定有序才能二分)
# ix = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
data = [9, 6, 5, 4, 2, 1, 3, 6, 7, 8, 9]
def bin_search(d):
start, end = 0, len(d) - 1
# 处理特殊情况头和尾
if d[start] < d[start + 1]: # [1,2,3]
return start
elif d[end] < d[end - 1]: # [3,2,1]
return end
idx = -1
while start <= end:
# mid = (start + end) // 2
# >> 1也可以写成 // 2, 为什么不用上面那个，因为 start + end 可能内存溢出，而 end 和 start 不会溢出，end - start 也不会
mid = start + ((end - start) >> 1)
# print(start, end, mid, data[mid])
if d[mid - 1] < d[mid] < d[mid + 1]: # / mid /
end = mid - 1
elif d[mid + 1] < d[mid] < d[mid - 1]: # \ mid \
start = mid + 1
else:
idx = mid
break
return idx
print(bin_search(data))
对数器的概念和使用
- 1，有一个你想要测的方法a
- 2，实现复杂度不好但是容易实现的方法b
- 3，实现一个随机样本产生器
- 4，把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。
- 5，如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者方法b
- 6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
比如使用冒泡、插入排序等与Python自带的sort对比
额外知识点异或运算
- 相同为0，不同为1，也可以理解为无进位相加，例：
1010 ^ 0110 = 1100 异或性质
0 ^ N = N；N ^ N = 0- 满足交换律和结合律：
a^b = b^a；(a^b)^c = a^(b^c)
根据上面性质可以不用额外变量交换2个值，前提条件：
这2个值在内存里面是2块独立的区域，否则会把值重置为0，及上面的性质：N ^ N = 0
a, b = 1, 2
a = a ^ b
b = a ^ b # b = a ^ b ^ b, 结合律：b=a
a = a ^ b # a= a ^ b; b = a; a = a ^ b ^ a，结合律：a=b
同一块内存交换
a = [[5]] * 3
a[0][0] = a[0][0] ^ a[1][0]
a[1][0] = a[0][0] ^ a[1][0]
a[0][0] = a[0][0] ^ a[1][0]
# a = [[0], [0], [0]]
异或题目1
- 一个整型数组中，已知只有一个数出现了奇数次，其他都出现了偶数次，找出出现了奇数次的数？要求时间复杂度 O(N)，空间复杂度O(1)
data = [1, 2, 1, 2, 3, 4, 4, 5, 7, 8, 9, 9, 8, 7, 6, 6]
eor = 0
for i in data:
eor ^= i
print(eor)
- 一个整型数组中，已知只有两个数出现了奇数次，其他都出现了偶数次，找出出现了两次奇数次的数？要求时间复杂度 O(N)，空间复杂度O(1)
data = [1, 2, 1, 2, 3, 4, 4, 5, 7, 8, 9, 9, 8, 7, 6, 6]
eor = 0
for i in data:
eor ^= i
"""
eor = a ^ b;
eor != 0
eor 必然有一个位置是1
eor: 1010111100
~eor: 0101000011
~eor+1: 0101000100
eor & (~eor+1): 0000000100 提取出最右侧的1
"""
right_one = eor & (~eor + 1) # 提取出最右侧的1
only_one = 0
for j in data:
# & 2个为1，才为1，否则为0
# if (right_one & j) == 0: # 筛选出那一位为0，与一下就为0了，例：101 & 010 = 000
if (right_one & j) == right_one: # 筛选出那一位也为1的值，例：110 & 010 = 010
# print(bin(j)[2:], bin(right_one)[2:])
only_one ^= j # a 或 b
print(only_one)
print(only_one ^ eor)