python常⽤算法，新⼿必会，⾯试必出
算法效率的度量⽅法
快速排序最常考
  事后统计⽅法：主要是通过设计好的测试程序和数据，利⽤计算机计时器对不同算法编制的程序的运⾏时间进⾏⽐较，从⽽确定算法效率的⾼低，但这种⽅法有很⼤缺陷，⼀般不予采纳。
  事前分析估算⽅法：在计算机程序编制前，依据统计⽅法对算法进⾏估算。
  ⼀个⽤⾼级语⾔编写的程序在计算机上运⾏时所消耗的时间取决于以下因素：
1. 算法采⽤的策略，⽅法；（算法好坏的根本）
2. 编译产⽣的代码质量；（由软件来⽀持）
3. 问题的输⼊规模；（由数据决定）
4. 机器执⾏指令的速度。（看硬件的性能）
算法时间复杂度
  定义：在进⾏算法分析时，语句总的执⾏次数T(n)是关于问题规模n的函数，进⽽分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n}=0(f(n))。它表⽰随问题规模n的增⼤，算法执⾏时间的埔长率和 f(n)的埔长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f( n)是问题规横n的某个函数。
根据定义，求解算法的时间复杂度的具体步骤是：
  ⑴ 出算法中的基本语句；
  算法中执⾏次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
  ⑵ 计算基本语句的执⾏次数的数量级；
  只需计算基本语句执⾏次数的数量级，这就意味着只要保证基本语句执⾏次数的函数中的最⾼次幂正确即可，可以忽略所有低次幂和最⾼次幂的系数。这样能够简化算法分析，并且使注意⼒集中在最重要的⼀点上：增长率。
  ⑶ ⽤⼤Ο记号表⽰算法的时间性能。
  将基本语句执⾏次数的数量级放⼊⼤Ο记号中。
如何推导⼤o阶呢？下⾯是基本的推导⽅法：
  1.⽤常数1取代运⾏时间中的所有加法常数。
  2.在修改后的运⾏次数函数中，只保留最髙阶项。
  3.如果最⾼阶项存在且不是1，则去除与这个项相乘的常数。
简单的说，就是保留求出次数的最⾼次幂，并且把系数去掉。  如T(n)=n2+n+1 =O(n2)
⼀些例⼦
>#复杂度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)
>#复杂度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)
原理：
1. ⽐较相邻的元素，如果第⼀个⽐第⼆个⼤，就交换他们两个；
2. 对每⼀对相邻元素做同样的⼯作，从开始第⼀对到结尾的最后⼀对。做完以后，最后的元素会是最⼤的数，这⾥可以理解为⾛了⼀
趟；
3. 针对所有的元素重复以上的步骤，除了最后⼀个；
4. 持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较，最后数列就是从⼤到⼩⼀次排列；
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)
python新手代码例子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)
原理：
1. 每⼀次从待排序的列表中选出⼀个元素，并将其与其他数依次⽐较，若列表中的某个数⽐选中的数⼩，则交换位置，把所有数⽐较完
毕，则会选出最⼩的数，将其放在最左边（这⼀过程称为⼀趟）；
2. 重复以上步骤，直到全部待排序的数据元素排完；
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
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]
插⼊排序
效率：O(n2)
原理：
1. 以从⼩到⼤排序为例，元素0为第⼀个元素，插⼊排序是从元素1开始，尽可能插到前⾯。
2. 插⼊时分插⼊位置和试探位置，元素i的初始插⼊位置为i，试探位置为i-1，在插⼊元素i时，依次与i-1,i-2······元素⽐较，如
果被试探位置的元素⽐插⼊元素⼤，那么被试探元素后移⼀位，元素i插⼊位置前移1位，直到被试探元素⼩于插⼊元素或者插⼊元素位于第⼀位。
3. 重复上述步骤，最后完成排序
demo：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。

less函数_教程|十分钟学会函数式Python!
« 上一篇
python案例代码解析
下一篇 »

发表评论

Copyright © 2024 baidu.com
Powered By 688IT编程网 豫ICP备2022007602号 豫公网安备41160202000602