1、什么是算法
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
一个算法应该具有以下七个重要的特征：
①有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
②确切性(Definiteness)：算法的每一步骤必须有确切的定义；
③输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
④输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
⑤可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）；
⑥高效性(High efficiency)：执行速度快，占用资源少；
⑦健壮性(Robustness)：对数据响应正确。
2、时间复杂度
计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间,时间复杂度常用大O符号（大O符号（Big O notation）是用于描述函数渐进行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。）表述，使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。
大O，简而言之可以认为它的含义是“order of”（大约是）。
无穷大渐近
大O符号在分析算法效率的时候非常有用。举个例子，解决一个规模为 n 的问题所花费的时间（或者所需步骤的数目）可以被求得：T(n) = 4n^2 - 2n + 2。
当 n 增大时，n^2; 项将开始占主导地位，而其他各项可以被忽略——举例说明：当 n = 500，4n^2; 项是 2n 项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。
简单来说时间复杂度是用来估计算法运行时间的一个式子（单位）。
时间复杂度高的算法比复杂度低的算法慢。
常见的时间复杂度（按效率排序） O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
不常见的时间复杂度（看看就好） O(n!) O(2n) O(nn) …
如何一眼判断时间复杂度？ 循环减半的过程：O(logn)；几次循环就是n的几次方的复杂度
几种常见逻辑代码时间复杂度的示例：
print('Hello World') #时间复杂度为O(1)
print('Hello World') #O(1)
print('Hello Python')
print(‘Hello Algorithm’)
for i in range(n): #O(n)
print('Hello World')
for i in range(n): #O(n2)
for j in range(n):
print('Hello World')
for i in range(n): #O(n2)
print('Hello World’)
for j in range(n):
print('Hello World')
for i in range(n): #O(n2)
for j in range(i):
print('Hello World')
for i in range(n): #O(n3)
for j in range(n):
for k in range(n):
print('Hello World')
while n > 1: #O(log2n)或O(logn)
print(n)
n = n // 2
3、空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。
什么是空间换时间：
我们在写代码时，完全可以用空间来换取时间，比如说，要判断某某年是不是闰年，你可能会花一点心思写了一个算法，而且由于是一个算法，也就意味着，每次给一个年份，都是要通过计算得到是否是闰年的结果。还有另一个办法就是，事先建立一个有2 050个元素的数组（年数略比现实多一点），然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是1，如果不是值为0。这样，所谓的判断某一年是否是闰年，就变成了查找这个数组的某一项的值是多少的问题。此时，我们的运算是最小化了，但是硬盘上或者内存中需要存储这2050个0和1。
算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将快速排序和归并排序算法就属于这种情况。
通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好，其实要看你用在什么地方。
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)= O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。
关于O(1)的问题， O(1)是说数据规模和临时变量数目无关，并不是说仅仅定义一个临时变量。举例：无论数据规模多大，我都定义100个变量，这就叫做数据规模和临时变量数目无关。就是说空间复杂度是O(1)
当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
通常，我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时，通常都是指时间复杂度。
对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。
4、列表查找
列表查找主要模型：
从列表中查找指定元素
输入：列表、待查找元素
输出：元素下标或未查找到元素
一般分为两种方式
（1）、顺序查找
从列表第一个元素开始，顺序进行搜索，直到找到为止。
（2）、二分查找
从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
import time
import random
def cal_time(func): #该装饰器用来测量函数运行的时间
def wrapper(*args,**kwargs):
t1 = time.time()
res = func(*args,**kwargs)
t2 = time.time()
print("%s running time: %s secs." % (func.__name__, t2 - t1))
return res
return wrapper
@cal_time #顺序查找 复杂度O(n)
def line_search(data,val):
# for i in range(len(data)):
# if data[i] == val:
# return i
for i in data:
if i == val:
return data.index(i)
return
@cal_time #二分查找 复杂度O(logn)
def bin_search(data_set, val):
#[1,2,3,4,5,6,7,8,9] val = 3
low = 0
high = len(data_set) - 1
while low <= high:
mid = (low+high)//2
if data_set[mid] == val:
return mid
elif data_set[mid] < val:
low = mid + 1
else:
high = mid - 1
return
data = list(range(100000000))
line_search(data,1733333)
bin_search(data,1733333)
上述代码执行结果为：
line_search running time: 0.04680013656616211 secs. bin_search running time: 0.0 secs.
练习：
现有一个学员信息列表（按id增序排列），格式为：
[
{id:1001, name:"张三", age:20},
{id:1002, name:"李四", age:25},
{id:1004, name:"王五", age:23},
{id:1007, name:"赵六", age:33}
]
修改二分查找代码，输入学生id，输出该学生在列表中的下标，并输出完整学生信息
代码实现：
def random_create_dict(n):
res = []
nid_list = list(range(1000,1000+n))
n1 = ['赵','钱','孙','李','周','吴','郑','王','慕容',]
n2 = ['国','富','明','强','帅','军','飞','','']
n3 = ['国', '富', '明', '强', '帅', '军', '飞', ]
for i in range(n):
arg = random.randint(16,60)
nid=nid_list[i]
name_list = random.choices(n1)+random.choices(n2)+random.choices(n3)
name = ''.join(name_list)
item = {'id':nid,'arg':arg,'name':name}
res.append(item)
return res
@cal_time
def bin_search_1(data_set, val):
low = 0
high = len(data_set) - 1
while low <= high:
mid = (low+high)//2
if data_set[mid]['id'] == val:
return mid
elif data_set[mid]['id'] < val:
low = mid + 1
else:
high = mid - 1
return
data = random_create_dict(999999)
n = bin_search_1(data,88888)
print(n,data[n])
5、排序
列表排序 ：
将无序列表变为有序列表
应用场景：
各种榜单
各种表格
给二分排序用
给其他算法用
输入：
无序列表
输出：
有序列表
（1）、常用的排序算法
低级排序算法： 冒泡排序 选择排序 插入排序
快速排序
高级排序算法： 堆排序 归并排序
没什么人用的排序： 基数排序 希尔排序 桶排序
冒泡排序（Bubble Sort）
import time,random
import copy
def cal_time(func): #该装饰器用来测量函数运行的时间
def wrapper(*args,**kwargs):
t1 = time.time()
res = func(*args,**kwargs)
t2 = time.time()
print("%s running time: %s secs." % (func.__name__, t2 - t1))
return res
return wrapper
@cal_time
def bubble_sort(li): #时间复杂度为O（n*n）
for i in range(len(li) - 1):
for j in range(len(li) - i - 1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
@cal_time
def bubble_sort_1(li):
for i in range(len(li) - 1):
exchange = False
for j in range(len(li) - i - 1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange:
break
@cal_time
def nor_sort(data):
list = sorted(data)
return list
data = list(range(10000))
random.shuffle(data)
data1 = copy.deepcopy(data)
data2 = copy.deepcopy(data)
bubble_sort_1(data)
bubble_sort(data1)
data2 = nor_sort(data2)
print(data)
选择排序
@cal_time
def select(data):
for i in range(len(data)-1):
min_loc = i
for j in range(i+1,len(data)):
if data[j] < data[min_loc]:
min_loc=j
data[i],data[min_loc] = data[min_loc],data[i]
插入排序(Insertion Sort)
插入排序(Insertion Sort)的基本思想是：将列表分为2部分，左边为排序好的部分，右边为未排序的部分，循环整个列表，每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
插入排序非常类似于整扑克牌。
在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。
也许你没有意识到，但其实你的思考过程是这样的：现在抓到一张7，把它和手里的牌从右到左依次比较，7比10小，应该再往左插，7比5大，好，就插这里。为什么比较了10和5就可以确定7的位置？为什么不用再比较左边的4和2呢？因为这里有一个重要的前提：手里的牌已经是排好序的。现在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌还可以用这个方法插入。编程对一个数组进行插入排序也是同样道理，但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。
@cal_time
def insert(data):
for i in range(1,len(data)):
temp = data[i]
j= i-1
while j>=0 and temp < data[j]:
data[j+1] = data[j]
j=j-1
data[j+1] = temp
source = [92, 77, 67, 8, 6, 84, 55, 85, 43, 67]
for index in range(1,len(source)):
current_val = source[index] #先记下来每次大循环走到的第几个元素的值
position = index
while position > 0 and source[position-1] > current_val: #当前元素的左边的紧靠的元素比它大,要把左边的元素一个一个的往右移一位,给当前这个值插入到左边挪一个位置出来
source[position] = source[position-1] #把左边的一个元素往右移一位
position -= 1 #只一次左移只能把当前元素一个位置 ,还得继续左移只到此元素放到排序好的列表的适当位置 为止
source[position] = current_val #已经找到了左边排序好的列表里不小于current_val的元素的位置,把current_val放在这里
print(source)