首页 / 算法 / python基本算法
python基本算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python基本算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5302字,纯文字阅读大概需要8分钟。
内容图文
![python基本算法](/upload/InfoBanner/zyjiaocheng/854/c88692e4c9904ae3bea89923a8395db6.jpg)
算法优劣评判标准
时间复杂度:
定义:用来评估算法运行效率的一个式子
print('Hello World') O(1)
for i in range(n):
print('Hello World') O(n)
for i in range(n):
for j in range(n):
print('Hello World') O(n^2)
for i in range(n):
for j in range(n):
for k in range(n):
print('Hello World') O(n^3)
注:O(1)、O(n)、O(n^2)..是一个单位,且当n足够大时,n^2的值可以忽略n的大小,所以计算时间复杂度时不会出现O(3)、O(n^2+n)的情况。
while n>1:
print(n)
n = n//2
输入:64
输出: 64 32 16 8 4 2
计算:2^6=64,执行次数6=log2 64
时间复杂度:O(logn)
小节:
时间复杂度是用来估计计算法运行时间的一个式子。
一般来说,时间复杂度高的算法比复杂度低的算法慢。
常见的时间复杂度(按效率排序)
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^2logn)<O(n^3)
复杂问题的时间复杂度
O(n!) O(2^n) O(n^n)
如何简单快速地判断算法复杂度
- 确定问题规模n
- 循环减半过程 -》 logn
- k层关于n的循环 n^k
复杂情况:根据算法执行过程判断
空间复杂度
定义:用来评估算法内存占用大小的式子
空间复杂的表示方式与实践复杂度完全一样
算法使用了几个变量:O(1)
算法使用了长度为n的一位列表:O(n)
算法使用了m行n列的二维列表:O(mn)
空间换时间
递归算法
递归的两个特点:
- 调用自身
- 结束条件
递归:汉诺塔问题
def hanoi(n,a,b,c):
if n>0:
hanoi(n-1,a,c,b)
print("moving [%s] from %s to %s" %(n,a,c))
hanoi(n-1,b,a,c)
hanoi(3,"a","b","c")
查找问题
查找:在一些数据元素中,通过一定的方法找出与给定关键字相同的数据元素的过程
列表查找(线性表查找):从列表中产兆指定元素
输入:列表、待查找元素
输出:元素下表(未找到元素之一般返回None或-1)
内置列表查找函数:index()
方法一:顺序查找
顺序查找:也叫线性查找,从列表第一个元素开始,顺序进行搜索,直到找到元素或搜索到列表最后一个元素为止。
# 顺序查找
def linear_search(li,val):
for i,v in enumerate(li):
if v == val:
return i
else:
return None
#i = linear_search([1,2,3,6,7],6)
#print(i)
复杂度:O(n)
方法二:二分查找
二分查找:又叫折半查找,从有序列表的初始候选区li[0:n]开始,通过对待查找的值与候选区中间值的比较,可以使候选区减少一半。
# 二分法查找
def binary_search(li,val):
left,right = 0,len(li)-1
while left<=right: # 候选区有值
mid = (left+right)//2
if li[mid]==val:
return mid
elif li[mid]<val:
left = mid+1
else:
right = mid=1
else:
return None
i = binary_search([1,2,3,6,7],10)
print(i)
复杂度:O(logn)
对比:使用二分查找的速度远远大于顺序查找,但是二分查找只能应用于线性排序的列表。
列表排序
排序:将一组“无序”的记录序列调整为“有序的记录序列”。
列表排序:将无序列表变为有序列表
输入:列表
输出:有序列表
升序和降序
内置排序函数:sort()
冒泡排序
列表每两个相邻的数,如果前面比后面大,则交换这两个数。
一趟排序完成后,则无序区减少一个数,有序区增加一个数。
代码关键:趟,无序区范围。
#冒泡排序
def bubble_sort(li):
for i in range(len(li)-1):
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
import random
li = [random.randint(1,1000) for _ in range(30)]
print(li)
bubble_sort(li)
print(li)
时间复杂度:O(n^2)
优化冒泡排序
#冒泡排序,当列表不再改变时 无需再循环
def bubble_sort(li):
for i in range(len(li)-1):
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
exchange = True
print(li)
if not exchange:
return
import random
li = [1,2,3,7,6,8,9]
print(li)
bubble_sort(li)
选择排序
每次选出列表中最大值或者最小值,放在列表的首位或者末尾。
def select_sort(li):
for i in range(len(li)-1):
min_loc = i
for j in range(i+1,len(li)):
if li[j]<li[min_loc]:
min_loc = j
li[min_loc],li[i] = li[i],li[min_loc]
li = [1,2,3,7,6,8,9]
print(li)
select_sort(li)
print(li)
插入排序
拿到手里的牌和之前的所有牌比较,如果比之前的牌小,则记录该位置,最后记录的值就是手里的牌正确排序后的位置。
def select_sort(li):
for i in range(len(li)-1):
min_loc = i
for j in range(i+1,len(li)):
if li[j]<li[min_loc]:
min_loc = j
li[min_loc],li[i] = li[i],li[min_loc]
li = [1,2,3,7,6,8,9]
print(li)
select_sort(li)
print(li)
快速排序
快速排序:快
快速排序思路:
取一个元素p(第一个元素),使元素p归位;
列表别p分成两部分,左边都比p小,右边都比p大;
递归完成排序。
def partition(li,left,right):
temp = li[left]
while left < right:
while left < right and li[right] >= temp:
right -= 1
li[left] = li[right]
while left < right and li[left] <= temp:
left += 1
li[right] = li[left]
li[left] = temp
return left
def quick_sort(li,left,right):
if left<right:
mid = partition(li,left,right)
quick_sort(li,left,mid-1)
quick_sort(li,left+1,right)
li = [9,4,3,6,8,15,3,31]
quick_sort(li,0,len(li)-1)
print(li)
快速排序的效率:
快速排序的时间复杂度 O(mlogn)
快速排序的问题:
最坏情况
递归
堆排序
树与二叉树
堆是一种特殊的完全二叉树
大根堆:一棵完全二叉树,满足任一节点都比其孩子节点大
小根堆:一棵完全二叉树,满足任一节点都比其孩子节点小
堆的向下调整:
假设:节点的左右子树都是堆,但是自身不是堆。
堆排序过程
堆排序过程:
- 建立堆。
- 得到堆顶元素,为最大元素。
- 去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整重新使堆有序。
- 堆顶元素为第二大元素。
- 重复步骤3,知道堆变空。
堆的向下调整
向下调整函数
def sift(li,low,high):
i = low
tmp = li[i]
j = i*2+1
while j<=high:
if j<high and li[j+1]>li[j]:
j = j+1
if tmp<=li[j]:
li[i]=li[j]
i = j
j = i*2+1
else:
break
li[i] = tmp
li = [1,9,8,7,6,5,0,2]
sift(li,0,len(li)-1)
print(li)
堆排序函数
def heap_sort(li):
n = len(li)
# 建堆
for i in range(n//2-1,-1,-1):
sift(li,i,n-1)
# 建堆完成
for i in range(n-1,-1,-1):
li[i],li[0]=li[0],li[i]
sift(li,0,i-1)
li = [2,6,4,6,8,5,3,10]
heap_sort(li)
print(li)
堆排序的内置模块heapq
import heapq
import random
li = list(range(100))
random.shuffle(li)
heapq.heapify(li)
print(li)
for i in range(len(li)-1):
print(heapq.heappop(li),end=' ')
归并排序
内容总结
以上是互联网集市为您收集整理的python基本算法全部内容,希望文章能够帮你解决python基本算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。