一.查找
时间复杂度是用来估算算法运行速度的一种方式，通常采用大O表示法。
需要注意以下几点：
-时间复杂度指的不是算法运行时间，而是算法运行的增速。
-时间复杂度是估算，一些非必要的会省略(比如复杂度的系数)。
-通常表示为O(n)，其中n为操作数。
快速判断时间复杂度的方法：
-如果发现循环数减半，那么复杂度就是logn；
-有几层的循环就是n的几次方，不要在意具体循环几(系数)次。
空间复杂度是对算法运行过程中临时占用存储空间大小的量度。
计算方法：(1)忽略常数，用O(1)表示；(2)递归的空间复杂度＝递归深度N＊每次递归所要的辅助空间；
递归
1.递归斐波那契数列
def fibnacci(n):
a=b=c=1
for i in range(2,n+1):
c=a+b
a=b
b=c
return c
print(fibnacci(10))
#打印89
2.递归实现汉诺塔
def hanoi(n,A,B,C):
if n> 0:
hanoi(n-1,A,B,C)
print('%s->%s' % (A,C))
hanoi(n-1,B,A,C)
查找
简单查找：就是按顺序查找，直到查到指定元素，时间复杂度为O(n)。
二分查找：就是对于简单查找的一种优化，但是只能对有序的数组有效，通过数组中间的数值和所需求的值比较，通过比较的结果来改变左右范围。
需要注意的是:不要通过切片改变列表，那样会加大空间复杂度。
尾递归的定义：尾递归就是所有递归语句都在函数的最后出现的，正常是相当于循环的复杂度，但是python内部没有优化。
二分法:
def mid_find(l,n):
left = 0
right = len(l)-1
while left <= right:
mid = (left + right) // 2
if l[mid] == n:
break
elif l[mid] < n:
left = mid +1
else:
right = mid -1
return -1
ls = [1,2,3,5,8,12,24,34,45,75,223]
mid_find(ls,75)
快速查找小技巧:新建列表作为索引,如果一个数的数值索引存在,那么这个数也存在
n = 7
l1 = [1,3,5,7] #在此列表中查询n是否存在
l2 = [0,0,0,0,0,0,0,0] #创建新列表,创建l1中最大数的数值+1个,列表内元素都为0
l3 = [0,1,0,1,0,1,0,1] #创建列表,l1中元素数值大小对应l3的索引元素数值为1
if l3[n] == 1:
print('n存在l1中')
else:
print('n不存在l1中')
排序
排序算法有稳定和不稳定之分;
稳定的排序是保证关键字相同的元素,排序之后相对位置不变,关键字就是排序的凭借,比如数字排序时的大小值;
排序算法的关键点是分为有序区和无序区的.
冒泡排序
因为越大的元素会经由交换慢慢'浮'到数列的顶端(升序或降序排列),就如同饮料中的CO2一样,故名冒泡.
原理:1.比较相邻的元素.如果第一个比第二个大,就交换他们两个;
2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该是最大的数;
3.针对所有的元素都重复以上的步骤,除了最后一个;
4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较.
def bubbleSort(nums):
for i in range(len(nums)-1): #循环n-1次
for j in range(len(nums)-i-1): #无序区的范围
if nums[j] > nums[j+1]: #判断大小,解构调换位置
nums[j],nums[j+1] = nums[j+1],nums[j]
return nums
nums = [5,2,45,6,8,2,1,43,34,21]
print(bubbleSort(nums))
选择排序
选择排序输出的是原序列的一个重排<a1,a2,a3,...,an*>，使得a1<=a2<=a3<=...<=an
def select_sort(l):
for i in range(len(l)-1):
min = i
for j in range(i+1,len(l)):
if l[j] < l[min]: #前后数值比较,min随着循环变化
min = j #如果后面的数比前面的数值小,那么调换位置
l[i],l[min] = l[min],l[i]
print(l)
lis = [1,2,12,3,123,34,121,354,23]
select_sort(lis)