1 概念
算法决定程序的效率
如何解决问题,如何提高效率,如何优化已有框架
问题
如果a+b+c=1000,且a2+b2=c^, 求a\b\c所有可能的组合?
以下算法耗时较长
# coding=utf-8
import time
start_time = time.time()
for a in range(1001):
for b in range(1001):
for c in range(1001):
if a+b+c==1000 and a**2+b**2==c**2:
print('a:',a, 'b:',b, 'c:',c)
end_time = time.time()
# 耗时: 200.12086462974548
print('耗时:',(end_time-start_time))
优化
# coding=utf-8
import time
start_time = time.time()
for a in range(1001):
for b in range(1001):
c = 1000-a-b
if a**2+b**2==c**2:
print('a:',a, 'b:',b, 'c:',c)
end_time = time.time()
# 耗时: 1.6905064582824707
print('耗时:',(end_time-start_time))
算法效率依赖于硬件和操作系统环境,可通过时间空间复杂度来评价算法的优劣
算法5大特征
1.0或多个输入
2.至少1个输出
3.确定性:每个指令清晰无意义
4.有穷性:有限个步骤,不能无线循环
5.可行性:能够精确运行
2 时间复杂度
算法花费时间与语句执行次数相关
以执行次数评价算法效率
对于1.1的算法1,执行次数
f(n) = n*n*n*2
对于1.1的算法2,执行次数
f(n) = n*n*3
实际中关注的是数量级和趋势,只关注最高次幂
渐进函数\渐进表示法:
T(n) = k*f(n) +c
则f(n)成为T(n)的渐进函数
O(f(n))为时间复杂读的渐进表示法
最优时间复杂度 | 最坏时间复杂度
如对列表[9,8,7,...,1]进行升序排序,则为最坏时间复杂度
如对列表[1,2,3,....9]进行升序排序,则为最优时间复杂度
如无特殊说明,则分析的时间复杂度为最坏
顺序结构按加法运算,循环结构按乘法计算,分支求最大值
判断一个算法效率,一般只关注最高次项
对于1.1中的两个算法的时间复杂度
算法1:O(n^3)
算法2:O(n^2)
算法2时间复杂度小于算法1
常见时间复杂度关系
O(1)<O(logn)<O(nlogn)<O(n2)<O(n3)<O(2n)O<O(nn)
3 空间复杂度
运行程序所需内存大小
固定部分+可变部分
固定部分:
代码,常量,变量等
可变部分:
动态分配的空间
优先考虑时间复杂度还是空间复杂度要看具体情况
复杂度通常指时间复杂度
4 排序算法
排序算法的稳定性
两个键值相等的记录相对位置不变
冒泡排序
1\2比较,大的向后交换
2\3比较,大的向后交换,
...
直至最后元素为最大
1\2比较,2\3比较,...,直至倒数第2个元素为次大
...
def bubble_sort(alist):
# 相邻元素比较,位置错误则交换
n = len(alist)
for k in range(n-1):
for i in range(n-1-k):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
时间复杂度:
最优O(n),最坏O(n^2)
冒牌排序优化
如果某一轮无交换,则列表已有序,退出循环
def bubble_sort(alist):
# 相邻元素比较,位置错误则交换
n = len(alist)
for k in range(n-1):
count = 0
for i in range(n-1-k):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
count += 1
if count == 0:
break
冒泡排序是稳定的
选择排序
选择出最小的放在首位
选择出次小的放在第2位
...
def select_sort(alist):
n = len(alist)
for i in range(n-1):
# 剩余列表中最小值的索引
min_index = i
for j in range(i+1, n):
if alist[j] < alist[min_index]:
min_index = j
if min_index != i:
alist[i],alist[min_index] = alist[min_index],alist[i]
时间复杂度:
最优和最坏都是O(n^2)
选择排序是不稳定的
插入排序
将列表分为有序无序两部分
第1个元素有序
1,2元素有序
1,2,3元素有序
...
当前元素与有序列表中每一个元素进行比较
def insert_sort(alist):
n = len(alist)
for j in range(1, n):
i = j
while i>0:
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
else:
break
i -= 1
时间复杂度:
最坏O(n^2),最优O(n)
插入排序是稳定的
快速排序
选取基准数据,小的放在左侧,大的放在右侧
def quick_sort(alist,start,end):
# 递归退出条件
if start >= end:
return
# 基准数
mid = alist[start]
low = start
high = end
while low<high:
while low<high and alist[high]>mid:
high-=1
alist[low] = alist[high]
while low<high and alist[low]<mid:
low+=1
alist[high] = alist[low]
alist[low]=mid
quick_sort(alist,start,low-1)
quick_sort(alist, low+1, end)
时间复杂度最优O(nlog(n)),最坏O(n^2)
快速排序不稳定
归并排序
先分解,再合并,每次合并保证有序
def merge_sort(alist):
# 分解
n = len(alist)
if n<=1:
return alist
mid = n//2
left_li = merge_sort(alist[0:mid])
right_li = merge_sort(alist[mid:])
# 合并
result = []
left_pointer,right_pointer=0,0
while left_pointer<len(left_li) and right_pointer < len(right_li):
if left_li[left_pointer] < right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer+=1
else:
result.append(right_li[right_pointer])
right_pointer+=1
# result += left_li[left_pointer:]
# extend比+效率更高
result.extend(left_li[left_pointer:])
# result += right_li[right_pointer:]
result.extend(right_li[right_pointer:])
return result
时间复杂度O(nlog(n)),无最优最坏
归并排序是稳定的
5 查找算法
5.1 顺序查找
def sequence_search(alist,v):
for i in range(len(alist)):
if alist[i] == v:
return i
return -1
5.2 二分查找
前提元素有序,首先比较中间元素和要查找元素
然后在左侧列表或者右侧列表查找元素
二分查找-递归方式
无法获取具体的下标?
def binary_search(alist,v):
mid_index = len(alist)//2
# 递归出口
if len(alist) == 0:
return False
if alist[mid_index] > v:
return binary_search(alist[0:mid_index],v)
elif alist[mid_index] < v:
return binary_search(alist[mid_index+1:], v)
else:
return True
另外,可以采用循环的方式
网友评论