Python算法基础
一、简介定义和特征定义:算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 一个算法应该具有以下五个重要的特征: 设计要求算法设计的要求:?
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) 一些例子
(<span style="color: #008000;">######复杂度O(n)
<span style="color: #0000ff;">for i <span style="color: #0000ff;">in<span style="color: #000000;"> range(n): <span style="color: #0000ff;">print<span style="color: #000000;">(i) <span style="color: #008000;">#<span style="color: #008000;">#####复杂度O(n2) <span style="color: #0000ff;">for i <span style="color: #0000ff;">in<span style="color: #000000;"> range(n): <span style="color: #0000ff;">for j <span style="color: #0000ff;">in<span style="color: #000000;"> range(n): <span style="color: #0000ff;">print<span style="color: #000000;">(j) <span style="color: #008000;">#<span style="color: #008000;">#####复杂度O(n3) <span style="color: #008000;">#<span style="color: #008000;">#####复杂度O(log2n) 常见的复杂度按效率排序:O(1) 空间复杂度?空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,这种算法是节省存储的算法;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元。 如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(log2n);当一个算法的空间复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。? 二、python中的常见算法冒泡排序效率:O(n2) 原理: demo:
i range(len(data)-1):
j range(len(data)-i-1):
data[j]>data[j+1]:
data[j],data[j+1]=data[j+1],data[j]
<span style="color: #0000ff;">if <span style="color: #800080;">name==<span style="color: #800000;">'<span style="color: #800000;">main<span style="color: #800000;">'<span style="color: #000000;">:<span style="color: #0000ff;">import<span style="color: #000000;"> random data_list=list(range(30<span style="color: #000000;">)) random.shuffle(data_list) <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">pre:<span style="color: #800000;">"<span style="color: #000000;">,data_list) bubble_sort(data_list) <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">after:<span style="color: #800000;">"<span style="color: #000000;">,data_list) <span style="color: #008000;">#<span style="color: #008000;">结果:<span style="color: #008000;"> <span style="color: #008000;">pre: [22,11,19,16,12,18,20,28,27,4,21,10,9,7,1,6,5,29,8,17,26,13,14,15,24,25,23,3,2]<span style="color: #008000;"><span style="color: #008000;">after: [0,2,22,29]优化版本:当某一趟走完以后发现并没有进行数据交换,那么此时的数列已经排列好了,没有必要在进行下去。例如:极端情况下,数列本来已经排序好的,我们只需要走一趟即可完成排序。
i range(len(data)-1):
exchange=False
j range(len(data)-i-1):
data[j]>data[j+1]:
data[j],data[j]
exchange = True
exchange:
i
<span style="color: #0000ff;">if <span style="color: #800080;">name==<span style="color: #800000;">'<span style="color: #800000;">main<span style="color: #800000;">'<span style="color: #000000;">:data_list=list(range(30<span style="color: #000000;">)) <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">pre:<span style="color: #800000;">"<span style="color: #000000;">,data_list) num =<span style="color: #000000;">bubble_sort(data_list) <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">after:<span style="color: #800000;">",data_list,<span style="color: #800000;">'<span style="color: #800000;">趟数:<span style="color: #800000;">',num+1<span style="color: #000000;">) <span style="color: #008000;">#<span style="color: #008000;">结果:<span style="color: #008000;"> <span style="color: #008000;">pre: [0,29]<span style="color: #008000;"> <span style="color: #008000;">after: [0,29] 趟数: 1 选择排序效率:O(n2) 原理:
demo:
i range(len(data)-1):
min_index=i
j range(i+1,len(data)):
data[j] < data[min_index]:
min_index==data[min_index],data[i]
<span style="color: #0000ff;">if <span style="color: #800080;">name==<span style="color: #800000;">'<span style="color: #800000;">main<span style="color: #800000;">'<span style="color: #000000;">:<span style="color: #0000ff;">import<span style="color: #000000;"> random data_list=list(range(30<span style="color: #000000;">)) random.shuffle(data_list) <span style="color: #008000;">#<span style="color: #008000;"> 打乱列表数据 <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">pre:<span style="color: #800000;">"<span style="color: #000000;">,data_list) select_sort(data_list) <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">after:<span style="color: #800000;">"<span style="color: #000000;">,data_list) <span style="color: #008000;">#<span style="color: #008000;">结果:<span style="color: #008000;"> <span style="color: #008000;">pre: [20,6]<span style="color: #008000;"><span style="color: #008000;">after: [0,29]插入排序效率:O(n2) 原理:
demo:
i range(1,len(data)):
tmp = data[i]
j range(i,-1,-1 tmp < data[j - 1]:
data[j] = data[j - 1]
:
= tmp
<span style="color: #0000ff;">if <span style="color: #800080;">name==<span style="color: #800000;">'<span style="color: #800000;">main<span style="color: #800000;">'<span style="color: #000000;">:<span style="color: #0000ff;">import<span style="color: #000000;"> random data_list=list(range(30<span style="color: #000000;">)) random.shuffle(data_list) <span style="color: #008000;">#<span style="color: #008000;"> 打乱列表数据 <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">pre:<span style="color: #800000;">"<span style="color: #000000;">,data_list) insert_sort(data_list) <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">after:<span style="color: #800000;">"<span style="color: #000000;">,data_list) <span style="color: #008000;">#<span style="color: #008000;">结果:<span style="color: #008000;"> <span style="color: #008000;">pre: [7,8]<span style="color: #008000;"> <span style="color: #008000;">after: [0,29] 快速排序效率:平均O(nlogn) 原理:
? ? ?? demo: <span style="color: #0000ff;">def <span style="color: #000000;"> quick_sort(data,left,right):<span style="color: #800000;">"""<span style="color: #800000;"> 快速排序 :param data: 待排序的数据列表 :param left: 基准数左边元素的索引 :param right: 基准数右边元素的索引 :return: <span style="color: #800000;">""" <span style="color: #0000ff;">if left <<span style="color: #000000;"> right: mid = partition(data,right) <span style="color: #008000;">#<span style="color: #008000;"> 分区操作,mid代表基数所在的索引 quick_sort(data,mid-1) <span style="color: #008000;">#<span style="color: #008000;"> 对基准数前面进行排序 quick_sort(data,mid+1,right) <span style="color: #008000;">#<span style="color: #008000;"> 对基准数后面进行排序 <span style="color: #0000ff;">def<span style="color: #000000;"> partition(data,right): <span style="color: #0000ff;">if <span style="color: #800080;">name==<span style="color: #800000;">'<span style="color: #800000;">main<span style="color: #800000;">'<span style="color: #000000;">: 堆排序堆定义:本质是一个完全二叉树,如果根节点的值是所有节点的最小值称为小根堆,如果根节点的值是所有节点的最大值,称为大根堆。 效率:O(nlogn) 原理:
? ? ?? demo: == 2 * i
tmp = data[i]
j <= j < high data[j] < data[j + 1]:
j += 1
tmp < data[j]:
data[i] == j
j = 2 *
data[i] = tmp
<span style="color: #0000ff;">def <span style="color: #000000;"> heap_sort(data):<span style="color: #800000;">"""<span style="color: #800000;"> 堆排序 :param data: 待排序的数据列表 :return: <span style="color: #800000;">"""<span style="color: #000000;"> n =<span style="color: #000000;"> len(data) <span style="color: #0000ff;">for i <span style="color: #0000ff;">in range(n // 2 - 1,-1<span style="color: #000000;">): sift(data,i,n - 1<span style="color: #000000;">) <span style="color: #008000;">#<span style="color: #008000;"> 构建堆 <span style="color: #0000ff;">for i <span style="color: #0000ff;">in range(n - 1,-1): <span style="color: #008000;">#<span style="color: #008000;"> 调整过程,从最后一个元素开始交换 data[0],data[i] = data[i],data[0] <span style="color: #008000;">#<span style="color: #008000;"> 交换 sift(data,i - 1) <span style="color: #008000;">#<span style="color: #008000;"> 开始调整 <span style="color: #0000ff;">if <span style="color: #800080;">name == <span style="color: #800000;">'<span style="color: #800000;">main<span style="color: #800000;">'<span style="color: #000000;">:<span style="color: #0000ff;">import<span style="color: #000000;"> random data_list = [1,66<span style="color: #000000;">] random.shuffle(data_list) <span style="color: #008000;">#<span style="color: #008000;"> 打乱列表数据 <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">pre:<span style="color: #800000;">"<span style="color: #000000;">,data_list) heap_sort(data_list) <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">after:<span style="color: #800000;">"<span style="color: #000000;">,data_list) <span style="color: #008000;">#<span style="color: #008000;">结果:<span style="color: #008000;"> <span style="color: #008000;">pre: [66,50]<span style="color: #008000;"><span style="color: #008000;">after: [1,66]归并排序效率:O(nlogn) 空间复杂度:O(n) 原理: ? ? ?? demo: = low
j = mid + 1
tmp = []
i <= mid j <= high:
data[i] <+= 1
j += 1
<span style="color: #000000;"> tmp.append(data[i]) <span style="color: #0000ff;">while j <= high: <span style="color: #008000;">#<span style="color: #008000;"> 右边有剩下 <span style="color: #000000;"> tmp.append(data[j]) j += 1<span style="color: #000000;"> data[low:high + 1] = tmp <span style="color: #008000;">#<span style="color: #008000;"> 最后将tmp中的数写入到原来的列表中 <span style="color: #0000ff;">def <span style="color: #000000;"> merge_sort(data,high):<span style="color: #800000;">"""<span style="color: #800000;"> 归并排序 :param data: 待排序的数据列表 :param low: 数据列表开始位置 :param high: 数据列表结束位置 :return: <span style="color: #800000;">""" <span style="color: #0000ff;">if low < high: <span style="color: #008000;">#<span style="color: #008000;"> 至少有两个元素才进行 mid = (low + high) // 2 <span style="color: #008000;">#<span style="color: #008000;"> 分割 merge_sort(data,mid) <span style="color: #008000;">#<span style="color: #008000;"> 递归分割上一部分 merge_sort(data,mid + 1,high) <span style="color: #008000;">#<span style="color: #008000;"> 递归分割下一部分 merge(data,high) <span style="color: #008000;">#<span style="color: #008000;"> 合并 <span style="color: #0000ff;">if <span style="color: #800080;">name == <span style="color: #800000;">'<span style="color: #800000;">main<span style="color: #800000;">'<span style="color: #000000;">:<span style="color: #0000ff;">import<span style="color: #000000;"> random
<span style="color: #008000;">#<span style="color: #008000;">结果:<span style="color: #008000;"> <span style="color: #008000;">pre: [21,66,66]希尔排序效率:与增量有关,O(n1+£)其中<0£<1,如增量为2k-1 复杂度为O(n3/2) 原理:
= len(data) // 2
d1 > i = data[i]
j = i - d1
j >= 0 tmp < data[j]:
data[j + d1] = data[j]
j -= d1
data[j + d1] =//= 2
<span style="color: #0000ff;">if <span style="color: #800080;">name == <span style="color: #800000;">'<span style="color: #800000;">main<span style="color: #800000;">'<span style="color: #000000;">:<span style="color: #0000ff;">import<span style="color: #000000;"> random data_list = [1,data_list) shell_sort(data_list) <span style="color: #0000ff;">print(<span style="color: #800000;">"<span style="color: #800000;">after:<span style="color: #800000;">"<span style="color: #000000;">,data_list) <span style="color: #008000;">#<span style="color: #008000;">结果:<span style="color: #008000;"> <span style="color: #008000;">pre: [3,1]<span style="color: #008000;"> <span style="color: #008000;">after: [1,66] (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |