复杂度和简单排序算法文章目录复杂度和简单排序算法[toc]1.常数操作O ( 1 ) O(1)O(1)2.时间复杂度1.常数操作O ( 1 ) O(1)O(1)定义执行步骤固定和输入规模N NN无关耗时恒定。例子算术 / 位运算ab、x1变量赋值、比较if a5数组下标随机读取arr[5]固定次数循环如循环 10 次注意O OO只关心运算次数会不会随输入规模N变大而增长循环固定10次不管N NN是100还是10000永远只跑10轮总量是固定常数所以是O ( 1 ) O(1)O(1)。2.时间复杂度定义时间复杂度为一个算法流程中常数操作数量的一个指标。用来估算算法运行时间随输入规模N NN的增长趋势只关心数据量大时的最高阶主导项忽略常数、低次项、系数。例如如果计算出来的常数操作数为5 N 2 3 N 4 5N^23N45N23N4该算法时间复杂度就是O ( N 2 ) O(N^2)O(N2)。补充额外空间复杂度的定义只开固定几个临时变量空间和输入规模N NN无关。很好理解比如一个算法暂时引入list [0, 1]额外的常数操作跟N NN无关显然复杂度为O ( 1 ) O(1)O(1)。时间复杂度案例1——选择排序数组长度为N每次从未排序区间选出最小值放到有序区间末尾第 1 轮遍历全部N个元素找最小第 2 轮遍历剩余 (N-1) 个元素……第 (N-1) 轮只剩 2 个元素遍历 1 次那么加起来最高次项就是N 2 N^2N2。其它的数组访问、比较、交换全是常数操作O ( 1 ) O(1)O(1)累计起来的常数操作数最多也是c N 2 cN^2cN2这么多c cc为常数。时间复杂度就是O ( N 2 ) O(N^2)O(N2)。# 选择排序算法defselection_sort(mylist):foriinrange(0,len(mylist)):forjinrange(i1,len(mylist)):ifmylist[j]mylist[i]:mylist[i],mylist[j]mylist[j],mylist[i]returnmylist时间复杂度案例2——冒泡排序重复遍历待排序数组依次比较相邻两个元素如果前一个元素 后一个元素就交换两者每一轮遍历结束后当前未排序区间中最大的元素会像气泡一样 “浮” 到区间末尾因此得名冒泡。冒泡排序的时间复杂度也是O ( N 2 ) O(N^2)O(N2)。defbubble_sort(mylist):ilen(mylist)whilei!1:ii-1forjinrange(0,i):ifmylist[j1]mylist[j]:mylist[j],mylist[j1]mylist[j1],mylist[j]returnmylistprint(bubble_sort([5,2,4,6,8,0,-1,4,6,43,-42,3,53,53]))时间复杂度案例3——插入排序将数组划分为已排序区间和未排序区间第一个元素天然有序已排序区间为[arr[0]]剩余元素属于未排序区间依次取出未排序区间首元素向前遍历已排序区间把所有更大元素后移将当前元素插入到合适位置。每一轮遍历结束后已排序区间长度增加一位数组前端始终保持有序。插入排序的时间复杂度也是O ( N 2 ) O(N^2)O(N2)。definsertion_sort(mylist):foriinrange(0,len(mylist)):forjinrange(i,0,-1):ifmylist[j]mylist[j-1]:mylist[j],mylist[j-1]mylist[j-1],mylist[j]returnmylistprint(insertion_sort([5,2,4,6,8,8,-42,0,-1,4,6,43,-42,3,53,53]))# 结果:[-42, -42, -1, 0, 2, 3, 4, 4, 5, 6, 6, 8, 8, 43, 53, 53]可以发现插入排序会比选择排序和冒泡排序这两个算法更好选择排序和冒泡排序是严格的N 2 N^2N2量级的常数操作不管输入进来的列表是否内部已经有排好序的序列都要进行循环遍历依次比较而插入排序时间常数操作最差是N 2 N^2N2量级如碰到[1, 2, 3,]这样已经排好序的数组常数操作就是N NN量级。但是时间复杂度是按照最差情况来计算的所有插入排序的时间复杂度也是O ( N 2 ) O(N^2)O(N2)。
