时间复杂度
时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。
O(1)：n的0次方
示例1
print("my name")
示例2
print("my name")
print("oldsyang")
print("please")
这个地方按理推算应该是O(3n^0)，前边那个3是个虚数，我们一般不要，所以就是O(n0)，也就是O(1)
O(n)：n的1次方
示例1
for i in items:
print(i)
示例2
for i in items:
print(i)
print('89'+i)
上边案列2推算是n+1，由于只取大的，所以结果还是O(n)
O(n^2)：n的2次方
for i in items:
for j in items:
print(i,j)
O(n3)：n的3次方
for i in range(n):
for j in range(n):
for K in range(n):
print(i,j,K)
在时间复杂度里，一般我们取大的单位，比如n2+n，那就是O(n2)
O(logn)
如果你是初学者，可以粗暴的认为，有几层循环就是n的几次方，当然了这只是粗暴的认为，比如下面就不是：
while n>1:
print(n,end='')
n=n//2
如果n为128，则结果为128,64,32,16,8,4,2,1
这样就是每次少一半，表示为O(log(2)(N))，意思是以2为底，N的对数（求指数）。还有可能是每次减少三分之一。我们在这里都统一用O(logn)来表示复杂度
一般来说，时间复杂度高的比复杂度低的算法慢。当然快慢还跟很多条件有关，最主要的还是要看N的具体情况。
常见的时间复杂度（按效率排序）
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
二分查找
从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。也就是每次都会剔除掉一半的数据去查找。
如用二分算法找到3
image
def func(li,val):
low=0
high=len(li)-1
while low<=high:
mid=(low+high)//2
if li[mid]==val:
return mid
elif li[mid]<val:
low=mid+1
else:
high=mid-1
index=func([1,2,3,4,5],-1)
print(index)
示例：
现有一个学员信息列表（按id增序排列），格式为：
info = [
{"id": 3001, "name": "yangzai"},
{"id": 3002, "name": "oldsyang"},
{"id": 3004, "name": "dazhou"},
{"id": 3007, "name": "lijian"},
]
使用二分查找法实现，输入学生id，输出该学生在列表中的下标，并输出完整学生信息。
解答
info = [
{"id": 3001, "name": "yangzai"},
{"id": 3002, "name": "oldsyang"},
{"id": 3004, "name": "dazhou"},
{"id": 3007, "name": "lijian"},
]
def get_data(order_id):
low = 0
hign = len(info) - 1
while low <= hign:
mid = len(info) // 2
mid_id = info[mid].get("id")
if mid_id == order_id:
return "索引是：{0},详细信息{1}".format(mid,info[mid])
elif mid_id < order_id:
low = mid + 1
else:
hign = mid - 1
print(get_data(3004))
递归算法：
- 必须要有终止条件的函数
- 结束条件
正着打印：
def func(x):
if x>0:
print(x)
func(x-1)
func(4)
#-----------输出-----
4
3
2
1
倒着打印：
def func(x):
if x>0:
func(x-1)
print(x)
func(4)
#-----------输出-----
1
2
3
4
输出"大哥大哥大哥大哥我的饼干拿来拿来拿来拿来"
def func(x):
if x==0:
print("我的饼干",end="")
else:
print("大哥",end="")
func(x-1)
print("拿来",end="")
func(4)
列表排序
冒泡排序
复杂度是n的2次方
冒泡排序理解的关键点是有序区和无序区
有序区，是指已经排好了的
无序区，是剩下没有顺序的区域
思路：列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数。
如图：
image
def bubbling_sort(li):
for i in range(len(li)-1): # i是冒泡次数（第几趟）
is_exchane=False # 标识在这一次冒泡里是否被交换，如果没有被交换的，则如果已经是有序的了，则直接返回
for j in range(len(li)-i-1): # j是每次的指针位置。range(列表长度-第几次冒泡-1)：
if li[j]>li[j+1]:
li[j],li[j+1]=li[j+1],li[j]
is_exchane=True
if not is_exchane:
break
return li
#升序
print(bubbling_sort([4,23,45,45,231,12,0,31]))
在有优化的情况下，其最好的复杂度是O(n)，代表已经是排好的了，直接返回了
其最坏的情况和平均情况是O(n^2)
选择排序
复杂度是n的2次方
思路：
一趟遍历记录最小的数，放到第一个位置
再一趟遍历记录剩余列表中最小的数，继续放置
li=[4,6,5,3,8,9,1,10,34]
1.先从li中找到最小的数字1，放到最前面，也就是跟4做交换
li=[1,6,5,3,8,9,4,10,34]
这样的话有序区里只有一个数字1，而无序区从6开始到最后
2.再从无序区中找最小的数字3，往前放，跟无序区的最开始位置6做交换
li=[1,3,5,6,8,9,4,10,34]
这样的话有序区里有1和3，而无序区从5开始到最后
3....依次执行上面的操作，即可得到结果
def select_sort(li):
for i in range(len(li)-1): # i是代表找的第几趟
min_index=i
#找i位置到最后范围内最小的数
for j in range(i,len(li)):# i可以改为i+1，省去与自己比较
if li[j]<li[min_index]:
min_index=j
if min_index!=i: # 说明最小值发生了变化
li[min_index],li[i]=li[i],li[min_index]
return li
print(select_sort([4,23,45,3,12,0,31]))
代码解析：
1 第一个for是总共要跑多少趟
2 设置最小值索引为第几趟的索引：min_index=i；第0趟，初始最小值是索引0，最小值就是li[0]
3 第二个for是去剩余无序区找最小值的索引，取值范围是：range(第几趟,最后)；
3.1 第0趟，无序区从索引0（也就是数值4）开始，依次找比数值4小的值，23，45都比4大，跳过，3比4小，最小值索引min_index=j（3的索引），再接着找12比3大，跳过，找到0比3小，最小值索引min_index=j（0的索引）
，再接着找到最后31比0大，跳过，第0趟的检索完毕。
3.2 现在拿到了最小值（0）的索引（5），将最小值（0）放到有序区去，即第0趟处：li[5],li[0]=li[0],li[5]，得到[0,23,45,3,12,4,31]，现在的有序区只有0，无序区从23开始，接着开始第1趟的查找
3.3 第1趟，无序区从索引1（也就是数值23）开始，依次找比数值23小的值，45都比4大，跳过，3比23小，最小值索引min_index=j（3的索引），再接着找12比3大跳过，找到4和31都比3大跳过，第1趟的检索完毕。
3.4 现在拿到了最小值（3）的索引（3），将最小值（3）放到有序区去，即第1趟处：li[3],li[1]=li[1],li[3]，得到[0,3,45,23,12,4,31]，现在的有序区为0和3，无序区从45开始，接着开始第2趟的查找
3.5 第2趟.[0,3,45,23,12,4,31]----》无序区从数值45开始-----》[0,3,4,23,12,45,31]
3.6 第3趟.[0,3,4,23,12,45,31]----》无序区从数值23（索引为3）开始-----》[0,3,4,12,23,45,31]
3.7 第4趟.[0,3,4,12,23,45,31]----》无序区从数值23（索引为4）开始-----》[0,3,4,12,23,45,31]
3.8 第5趟.[0,3,4,12,23,45,31]....》无序区从数值45开始-----》[0,3,4,12,23,31,45]
插入排序
复杂度是n的2次方
思路：
列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。
image
def insert_sort(li):
for i in range(1,len(li)):# i代表每次取到的数字的下标
tmp=li[i] #临时存放起来（抽取一张牌）
j=i-1 #
while j>=0 and tmp < li[j]:
li[j+1]=li[j]
j-=1
li[j+1]=tmp
li=[5,7,3,4,1,9,8]
insert_sort(li)
print(li)
快速排序
复杂度是nlog(n)
思路：
取一个元素p（第一个元素），使元素p归位；
列表被p分成两部分，左边都比p小，右边都比p大；
递归完成排序。
image
思路解析
li=[5,7,4,6,3,1,2,9,8]
1 取第一个元素5归位，得到[2,1,4,3,5,6,7,9,8]，观察发现，归位之后，5左边的数都小于5，5右边的数都大于5
2.1 取5左边的数列表[2,1,4,3]，继续归位，取第一个元素2归位，得到[1,2,4,3]，观察发现2左边的数比2小，2右边的数比2大。
2.1.1 2左边只有一个数，不用再递归归位，取2右边的列表[4,3]继续归位，取第一个元素4归位，得到[3,4]
2.2 取5右边的数列表[6,7,9,8]，继续归位，取第一个元素6归位，得到[6,7,9,8]，观察发现6左边的数没有，6右边的数比6大。
2.2.1 取6右边的数列表[7,9,8]，继续归位操作，其第一个元素7归位，得到[7,9,8]，7左边的数没有，7右边的数比7大。
2.2.1.1 取7右边的数列表[9,8]，继续归位操作，其第一个元素9归位，得到[8,9]
3 归位结束
上面一直在说归位，这里的重点就是这个如何去归位
如图
image
归位解析：
li=[5,7,4,6,3,1,2,9,8]
1. 先取一个5出来，这样左边就有了一个空位，应该从后面的数中找个数来填上，因为5是要想办法去中间的位置，从上边的思路解析中看出应该从右边找一个比5小的数到左边去。那我们从最右边开始找.
1.1 8比5大，该留在右边不动，9比5大，该留在右边不动，2比5小，挪到左边去，得到[2,7,4,6,3,1,空位,9,8];
1.2 右边空了一个位置出来，应该从左边找一个比5大的数到这个空位填上，从左边7开始找，7比5大，挪到右边空位上，得到[2,空位,4,6,3,1,7,9,8]
1.3 左边有了空位，再从右边的1开始往前找比5小的数，1比5小，挪到左边的空位上，得到[2,1,4,6,3,空位,7,9,8]
1.4 右边有了空位，应该从左边找一个比5大的数到这个空位填上，从左边4开始找，4比5小跳过；6比5大，挪到右边空位上，得到[2,1,4,空位,3,6,7,9,8]
1.5 左边有了空位，再从右边的3开始往前找比5小的数，3比5小，挪到左边的空位上，得到[2,1,4,3,空位,6,7,9,8]
1.5 发现找完了之后，剩下一个空位，再将最开始的5放到这个位置上，得到[2,1,4,3,5,6,7,9,8]
2. 取2出来
代码：
def partition(li,left,right):
tmp=li[left]
while left<right:
# 从右侧开始找比tmp小的数往做填充
while left<right and li[right]>=tmp:# 如果比tmp大，指针往左移
right-=1
li[left]=li[right]
# 从左侧开始找比tmp大的数往右填充
while left<right and li[left]<=tmp:# 如果比tmp小，指针往右移
left+=1
li[right]=li[left]
# 将tmp填充到归位好之后的空位
li[left]=tmp # 或者li[right]=tmp
return left # right
def kuaipai(li,left,right):
if left < right:
mid=partition(li,left,right)
kuaipai(li,left,mid-1)
kuaipai(li,mid+1,right)
li=[5,6,7,1,4,9,8]
kuaipai(li,0,len(li)-1)
print(li)
注意：
列表里删除一个元素，其复杂度是O(n)，其内存是一块连续的空间，删除一个之后，要将删除元素之后的数据往前移，并列表长度减一。在写算法的时候，不能去使用内置的函数。
数据结构
列表和链表都是线性的数据结构，链表不是连续的存储，而列表一定是连续的存储
列表在内存中开辟了一块连续的空间存储数据（存储的是数据的内存地址）
链表中每一个元素都是一个对象，每个对象称为一个节点，包含有数据域key和指向下一个节点的指针next。通过各个节点之间的相互连接，最终串联成一个链表.
class Node(object):
def __init__(self, item):
self.item = item
self.next = None
n1=Node(1)
n2=Node(2)
n3=Node(3)
n1.next=n2
n2.next=n3
print(n1.next.item) # 2
链表的删除和插入操作很快。因为不管是插入和删除，实际最多操作的是两个项。
class Node(object):
def __init__(self, item):
self.item = item
self.next = None
n1=Node(1)
n2=Node(2)
n3=Node(3)
n1.next=n2
n2.next=n3
# 在1和2之间插入一条数据
n4=Node(4)
n4.next=n1.next
n1.next=n4
# 删除n2节点
p=n1.next
n1.next=p.next
del p
建链表
头插法
class Node(object):
def __init__(self, item=None):
self.item = item
self.next = None
def create_linklist(li):
head=Node()
for i in li:
s=Node(i)
s.next=head.next
head.next=s
return head
link=create_linklist([1,2,3,4,5])
print(link.item) # None
print(link.next.item) # 5
print(link.next.next.item) # 4
print(link.next.next.next.item) # 3
# 倒着排的
尾插法
class Node(object):
def __init__(self, item=None):
self.item = item
self.next = None
def create_linklist(li):
# 头部节点
head=Node()
# 尾部节点
r=head
for i in li:
s=Node(i)
r.next=s
r=s
return head
link=create_linklist([1,2,3,4,5])
print(link.item) # None
print(link.next.item) # 1
print(link.next.next.item) # 2
print(link.next.next.next.item) # 3
比较复杂度
按元素值查找：顺序查找是一样的，链表无法二分查找，因为没法下标查找
按下标查找：列表是O(1)，列表是O(n)
在某元素后插入：列表是O(n)，列表是O(1)
删除某元素：列表是O(n)，列表是O(1)
网友评论