一些例子
复制代码
复杂度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)
//代码效果参考：https://v.youku.com/v_show/id_XNjQwNjgxOTE5Mg==.html
复杂度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)
原理：
比较相邻的元素，如果第一个比第二个大，就交换他们两个；
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。做完以后，最后的元素会是最大的数，这里可以理解为走了一趟；
针对所有的元素重复以上的步骤，除了最后一个；
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较，最后数列就是从大到小一次排列；
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)
原理：
每一次从待排序的列表中选出一个元素，并将其与其他数依次比较，若列表中的某个数比选中的数小，则交换位置，把所有数比较完毕，则会选出最小的数，将其放在最左边（这一过程称为一趟）；
重复以上步骤，直到全部待排序的数据元素排完；
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
//代码效果参考：https://v.youku.com/v_show/id_XNjQwNjgyNDkyNA==.html
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]
复制代码
