python常用算法,新手必会,面试必出

简介: 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)

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:

def insert_sort(data):

"""

插入排序

:param data: 待排序的数据列表

:return:

"""

for i in range(1, len(data)): # 无序区域数据

tmp = data[i] # 第i次插入的基准数

for j in range(i, -1, -1):

if tmp < data[j - 1]: # j为当前位置,试探j-1位置

data[j] = data[j - 1] # 移动当前位置

else: # 位置确定为j

break

data[j] = tmp # 将当前位置数还原

 

if __name__=='__main__':

import random

data_list=list(range(30))

random.shuffle(data_list) # 打乱列表数据

print("pre:",data_list)

insert_sort(data_list)

print("after:",data_list)

#结果:

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

#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(nlogn)

原理:

  1. 从数列中随机挑选出一个数作为基数;
  2. 重新排列数列,使得比基数小的元素在左边,比基数大元素在右边,相等的元素放左边或者右边都可以,最后使得该基数在处于数列中间位置,这个称为分区操作;
  3. 递归上述操作,完成排序,如下如;

     

demo:

#!/usr/bin/env python3

#_*_ coding:utf-8 _*_

#Author:wd

 

def quick_sort(data,left,right):

"""

快速排序

:param data: 待排序的数据列表

:param left: 基准数左边元素的索引

:param right: 基准数右边元素的索引

:return:

"""

if left < right:

mid = partition(data,left,right) # 分区操作,mid代表基数所在的索引

quick_sort(data,left,mid-1) # 对基准数前面进行排序

quick_sort(data,mid+1,right) # 对基准数后面进行排序

 

 

def partition(data,left,right):

tmp=data[left] # 随机选择的基准数,从最左边开始选

while left < right:

while left < right and data[right] >= tmp: # 右边的数比基准数大

right-=1 # 保留该数,然后索引指针往左移动

data[left]=data[right] # 否则此时右边数比基数小,则将该数放到基准位置

while left < right and data[left] <= tmp: # 右边的数比基准数小

left+=1 # 此时保持该数位置不动,索引指针往前移动

data[right]=data[left] # 否则此时左边的数比基数大,则将该数放到右边

data[left] = tmp # 最后将基准数量放回中间

return left # 返回基准数位置

 

if __name__=='__main__':

data_list=[1,3,21,6,50,33,34,58,66]

quick_sort(data_list,0,len(data_list)-1)

print(data_list)

###结果:[1, 3, 6, 21, 33, 34, 50, 58, 66]

堆排序

堆定义:本质是一个完全二叉树,如果根节点的值是所有节点的最小值称为小根堆,如果根节点的值是所有节点的最大值,称为大根堆。

效率:O(nlogn)

原理:

  1. 将待排序数据列表建立成堆结构(建立堆);
  2. 通过上浮(shift_up)或下沉(shift_down)等操作得到堆顶元素为最大元素(已大根堆为例);
  3. 去掉堆顶元素,将最后的一个元素放到堆顶,重新调整堆,再次使得堆顶元素为最大元素(相比第一次为第二大元素);
  4. 重复3操作,直到堆为空,最后完成排序;

     

demo:

def sift(data, low, high):

"""

调整堆函数

:param data: 带排序的数据列表

:param low: 值较小的节点的位置,可以理解为是根节点

:param high:值较大的节点的位置

:return:

"""

i = low

j = 2 * i # 父节点i所对应的左孩子

tmp = data[i] # 最较小节点的值

while j <= high:

if j < high and data[j] < data[j + 1]: # 如果右孩子比左孩子大则把j指向右节点

j += 1 # 指向右节点

if tmp < data[j]: # 如果此时位置较小的节点值比该节点值小,则将该节点上浮最为新的父节点,并调整该节点双亲

data[i] = data[j]

i = j # 调整该节点的双亲的位置

j = 2 * i

else:

break # 否则代表本次调整已经完成,并且节点i已经无值

data[i] = tmp # 最后将被调整节点的值放到i节点上(空出的位置)

 

 

def heap_sort(data):

"""

堆排序

:param data: 待排序的数据列表

:return:

"""

n = len(data)

for i in range(n // 2 - 1, -1, -1):

sift(data, i, n - 1)

# 构建堆

for i in range(n - 1, -1, -1): # 调整过程,从最后一个元素开始交换

data[0], data[i] = data[i], data[0] # 交换

sift(data, 0, i - 1) # 开始调整

 

 

if __name__ == '__main__':

import random

data_list = [1, 3, 21, 6, 50, 33, 34, 58, 66]

random.shuffle(data_list) # 打乱列表数据

print("pre:", data_list)

heap_sort(data_list)

print("after:", data_list)

#结果:

#pre: [66, 3, 58, 34, 1, 33, 21, 6, 50]

#after: [1, 3, 6, 21, 33, 34, 50, 58, 66]

归并排序

效率:O(nlogn)

空间复杂度:O(n)

原理:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
  4. 重复步骤3直到某一指针达到序列尾;
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

     

demo:

def merge(data, low, mid, high):

"""

合并函数

:param data: 数据列表
:param low: 列表开头位置
:param mid: 分割中间位置
:param high: 列表最后位置
:return:
"""
i = low # 第一个指针
j = mid + 1 # 第二个指针
tmp = [] # 临时存放的列表
while i <= mid and j <= high: # 分割的列表当两边都有数才进行
if data[i] < data[j]:
tmp.append(data[i])
i += 1 # 低的指针往右移动
else:
tmp.append(data[j]) # 右边大,存右边的数
j += 1 # 同时指针右移动
 
while i <= mid: # 左边分割有剩下 tmp.append(data[i])
i += 1
while j <= high: # 右边有剩下 tmp.append(data[j])
j += 1
data[low:high + 1] = tmp # 最后将tmp中的数写入到原来的列表中
 
 
def merge_sort(data, low, high):
"""

归并排序

:param data: 待排序的数据列表
:param low: 数据列表开始位置
:param high: 数据列表结束位置
:return:
"""
if low < high: # 至少有两个元素才进行
mid = (low + high) // 2 # 分割
merge_sort(data, low, mid) # 递归分割上一部分
merge_sort(data, mid + 1, high) # 递归分割下一部分
merge(data, low, mid, high) # 合并
 
 
if __name__ == '__main__':
import random
 
data_list = [1, 3, 21, 6, 50, 33, 34, 58, 66]
random.shuffle(data_list) # 打乱列表数据
print("pre:", data_list)
merge_sort(data_list, 0, len(data_list) - 1)
print("after:", data_list)
 
#结果:
#pre: [21, 3, 33, 58, 34, 66, 1, 6, 50]
#after: [1, 3, 6, 21, 33, 34, 50, 58, 66]

希尔排序

效率:与增量有关,O(n1+£)其中<0£<1,如增量为2k-1 复杂度为O(n3/2)

原理:

  1. 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。
  2. 先在各组内进行直接插入排序;
  3. 取第二个增量d2<d1重复上述的分组和排序,直至所取的增量  =1(  <  …<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

def shell_sort(data):
"""
希尔排序
:param data:待排序的数据列表
:return:
"""
d1 = len(data) // 2 # 设置分割大小为d1,
while d1 > 0:
for i in range(d1, len(data)):
tmp = data[i] # 当前分割元素位置
j = i - d1 # 上一个分割元素位置
while j >= 0 and tmp < data[j]: # 上一个元素分割位置比当前分割位置要大,则需要调整位置
data[j + d1] = data[j] # 后移动当前分割元素位置
j -= d1 # 往前移d1
data[j + d1] = tmp
d1 //= 2 # 继续分割
 
 
if __name__ == '__main__':
import random
data_list = [1, 3, 21, 6, 50, 33, 34, 58, 66]
random.shuffle(data_list) # 打乱列表数据
print("pre:", data_list)
shell_sort(data_list)
print("after:", data_list)
#结果:
#pre: [3, 66, 58, 34, 33, 50, 6, 21, 1]
#after: [1, 3, 6, 21, 33, 34, 50, 58, 66]
目录
相关文章
|
18天前
|
机器学习/深度学习 人工智能 算法
猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
宠物识别系统使用Python和TensorFlow搭建卷积神经网络,基于37种常见猫狗数据集训练高精度模型,并保存为h5格式。通过Django框架搭建Web平台,用户上传宠物图片即可识别其名称,提供便捷的宠物识别服务。
201 55
|
7天前
|
存储 缓存 监控
局域网屏幕监控系统中的Python数据结构与算法实现
局域网屏幕监控系统用于实时捕获和监控局域网内多台设备的屏幕内容。本文介绍了一种基于Python双端队列(Deque)实现的滑动窗口数据缓存机制,以处理连续的屏幕帧数据流。通过固定长度的窗口,高效增删数据,确保低延迟显示和存储。该算法适用于数据压缩、异常检测等场景,保证系统在高负载下稳定运行。 本文转载自:https://www.vipshare.com
101 66
|
2月前
|
搜索推荐 Python
利用Python内置函数实现的冒泡排序算法
在上述代码中,`bubble_sort` 函数接受一个列表 `arr` 作为输入。通过两层循环,外层循环控制排序的轮数,内层循环用于比较相邻的元素并进行交换。如果前一个元素大于后一个元素,就将它们交换位置。
138 67
|
2月前
|
存储 搜索推荐 Python
用 Python 实现快速排序算法。
快速排序的平均时间复杂度为$O(nlogn)$,空间复杂度为$O(logn)$。它在大多数情况下表现良好,但在某些特殊情况下可能会退化为最坏情况,时间复杂度为$O(n^2)$。你可以根据实际需求对代码进行调整和修改,或者尝试使用其他优化策略来提高快速排序的性能
128 61
|
2月前
|
算法 数据安全/隐私保护 开发者
马特赛特旋转算法:Python的随机模块背后的力量
马特赛特旋转算法是Python `random`模块的核心,由松本真和西村拓士于1997年提出。它基于线性反馈移位寄存器,具有超长周期和高维均匀性,适用于模拟、密码学等领域。Python中通过设置种子值初始化状态数组,经状态更新和输出提取生成随机数,代码简单高效。
117 63
|
28天前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
153 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
|
11天前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
47 20
|
3天前
|
算法 网络协议 Python
探秘Win11共享文件夹之Python网络通信算法实现
本文探讨了Win11共享文件夹背后的网络通信算法,重点介绍基于TCP的文件传输机制,并提供Python代码示例。Win11共享文件夹利用SMB协议实现局域网内的文件共享,通过TCP协议确保文件传输的完整性和可靠性。服务器端监听客户端连接请求,接收文件请求并分块发送文件内容;客户端则连接服务器、接收数据并保存为本地文件。文中通过Python代码详细展示了这一过程,帮助读者理解并优化文件共享系统。
|
8天前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
40 5
|
2月前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用