Python算法基础教程

简介: Python算法基础教程

一些例子
复制代码

复杂度O(1)

print("this is wd")

复杂度O(n)

for i in range(n):
print(i)

复杂度O(n2)

for i in range(n):
for j in range(n):
print(j)
//代码效果参考:https://v.youku.com/v_show/id_XNjQwNjgxOTE5Mg==.html

复杂度O(n3)

for i in range(n):
for j in range(n):
for k in range(n):
print('wd')

复杂度O(log2n)

while n > 1:
print(n)
n = n // 2
复制代码
常见的复杂度按效率排序:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2nlogn)<O(n2)

空间复杂度
  空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,这种算法是节省存储的算法;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元。

如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(log2n);当一个算法的空间复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

二、python中的常见算法
冒泡排序
效率:O(n2)

原理:

比较相邻的元素,如果第一个比第二个大,就交换他们两个;
对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。做完以后,最后的元素会是最大的数,这里可以理解为走了一趟;
针对所有的元素重复以上的步骤,除了最后一个;
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较,最后数列就是从大到小一次排列;
demo:

复制代码
def bubble_sort(data):
"""
冒泡排序
:param data:
:return:
"""
for i in range(len(data)-1): # 趟数
for j in range(len(data)-i-1): # 遍历数据,依次交换
if data[j]>data[j+1]: # 当较大数在前面
data[j],data[j+1]=data[j+1],data[j] #交换两个数的位置

if name=='main':
import random
data_list=list(range(30))
random.shuffle(data_list)
print("pre:",data_list)
bubble_sort(data_list)
print("after:",data_list)

结果:

pre: [22, 11, 19, 16, 12, 18, 20, 28, 27, 4, 21, 10, 9, 7, 1, 6, 5, 29, 8, 0, 17, 26, 13, 14, 15, 24, 25, 23, 3, 2]

after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

复制代码
优化版本:当某一趟走完以后发现并没有进行数据交换,那么此时的数列已经排列好了,没有必要在进行下去。例如:极端情况下,数列本来已经排序好的,我们只需要走一趟即可完成排序。

复制代码
def bubble_sort(data):
"""
冒泡排序优化版
:param data:
:return:
"""
for i in range(len(data)-1): # 趟数
exchange=False # 交换标志
for j in range(len(data)-i-1): # 遍历数据,依次交换
if data[j]>data[j+1]: # 当较大数在前面
data[j],data[j+1]=data[j+1],data[j] # 交换两个数的位置
exchange = True # 改变标志
if not exchange: # 如果某一趟没有进行交换,代表排序完成
break
return i # 返回次数的趟数

if name=='main':
data_list=list(range(30))
print("pre:",data_list)
num =bubble_sort(data_list)
print("after:",data_list,'趟数:',num+1)

结果:

pre: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29] 趟数: 1

复制代码
选择排序
效率:O(n2)

原理:

每一次从待排序的列表中选出一个元素,并将其与其他数依次比较,若列表中的某个数比选中的数小,则交换位置,把所有数比较完毕,则会选出最小的数,将其放在最左边(这一过程称为一趟);
重复以上步骤,直到全部待排序的数据元素排完;
demo:

复制代码
def select_sort(data):
"""
选择排序
:param data: 待排序的数据列表
:return:
"""
for i in range(len(data)-1): #趟数
min_index=i # 记录i趟开始最小的数的索引,我们从最左边开始
for j in range(i+1,len(data)): # 每一次趟需要循环的次数
if data[j] < data[min_index]: # 当数列中的某一个数比开始的数要小时候,更新最小值索引位置
min_index=j
//代码效果参考:https://v.youku.com/v_show/id_XNjQwNjgyNDkyNA==.html

    data[i],data[min_index]=data[min_index],data[i]  # 一趟走完,交换最小值的位置,第一趟最小

if name=='main':
import random
data_list=list(range(30))
random.shuffle(data_list) # 打乱列表数据
print("pre:",data_list)
select_sort(data_list)
print("after:",data_list)

结果:

pre: [20, 11, 22, 0, 18, 21, 14, 19, 7, 23, 27, 29, 24, 4, 17, 15, 5, 10, 26, 13, 25, 1, 8, 16, 3, 9, 2, 28, 12, 6]

after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

复制代码

相关文章
|
4天前
|
数据采集 小程序 数据库
20年“镇国级”IT大牛,竟搞出500页漫画Python零基础顶级教程!
乔布斯说每个人都应该学习一门编程语言。Python正热,我决定通过编程让自己习得一种思考问题的方式,这也是我在个人编程生涯中的最大收获。 我以为只能枯燥无味地学编程,直到看到本书的样章,以漫画形式让我更直观、生动地了解到什么是编程。超级喜欢这种漫画风格。我回想起自己当年学习编程语言时的情景:逼迫自己背诵和消化、吸收那些自己根本没有理解的内容。如果当时有这么一本书,我就不会学得那么艰难,然后用了那么久才摸索成为一名“攻城狮”。
|
3天前
|
算法 测试技术 Python
python中算法无限循环(Infinite Loops)
【7月更文挑战第18天】
20 4
|
4天前
|
算法 IDE 测试技术
Python中算法错误
【7月更文挑战第17天】
14 4
|
3天前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
【7月更文挑战第19天】Trie树,又称前缀树,是优化字符串搜索的高效数据结构。通过利用公共前缀,Trie树能快速插入、删除和查找字符串。
16 2
|
3天前
|
算法 搜索推荐 测试技术
python中算法逻辑错误(Logic Errors)
【7月更文挑战第18天】
7 2
|
3天前
|
算法 Python
python中算法递归错误(Recursion Errors)
【7月更文挑战第18天】
8 1
|
4天前
|
算法 计算机视觉 Python
Python并查集大揭秘:让你在算法界呼风唤雨,秒杀一切复杂场景!
【7月更文挑战第18天】并查集是Python中解决集合动态合并与查询的利器,常用于复杂问题。例如,在社交网络中快速判断用户是否在同一朋友圈,通过路径压缩优化的`UnionFind`类实现。另外,计算图像中岛屿数量也可借助并查集,将相邻像素合并成集合。并查集的应用显示了其在算法中的高效和灵活性,是提升编程技能的关键工具。
10 2
|
4天前
|
并行计算 算法 Python
Dantzig-Wolfe分解算法解释与Python代码示例
Dantzig-Wolfe分解算法解释与Python代码示例
|
5天前
|
存储 算法 Python
火箭般的提升!学会Python并查集,让你的算法能力飞跃新高度!
【7月更文挑战第17天】并查集,高效解决集合合并查询问题,常用于图的连通性判断。Python实现关键包含查找和合并操作。初始化时,元素各自为集合。查找使用路径压缩优化,合并则可选按秩策略保持平衡。例如,检测无向图环路,遍历边,若并查集发现边两端已在同一集合,则存在环。掌握并查集,提升算法能力,助你在问题解决中一飞冲天!动手实践,成为算法达人!
13 2
|
11天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战