复杂度和简单排序算法

文章目录

• • • 复杂度和简单排序算法
  • @[toc]
  • • • 1.常数操作O ( 1 ) O(1)O(1)
      • 2.时间复杂度

1.常数操作O ( 1 ) O(1)O(1)

定义：执行步骤固定，和输入规模N NN无关，耗时恒定。

例子：

1. 算术 / 位运算：a+b、x>>1
2. 变量赋值、比较：if a>5
3. 数组下标随机读取：arr[5]
4. 固定次数循环（如循环 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^2+3N+45N2+3N+4，该算法时间复杂度就是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(i+1,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):i=len(mylist)whilei!=1:i=i-1forjinrange(0,i):ifmylist[j+1]<mylist[j]:mylist[j],mylist[j+1]=mylist[j+1],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)。