python侯先⽣爬楼梯问题_python的算法
⼀、复习：
递归的两个特点：
1、调⽤⾃⾝。
2、结束条件。
1 1.deffunc1(x)
2 print(x)
3 func1(x-1)4
5
6 2.deffunc2(x)
7 if x>0:
8 print(x)
9 func2(x+1)10
11
12 3.deffunc3(x)13 if x>0:14 print(x)15 func3(x-1)16
17
18 4.deffunc4(x)19 if x>0:20 func4(x-1)21 print(x)
看上列代码如果是func1跟func2就是⽆限循环，没有合理的结束条件。func3跟func4就是有合理条件，可以循环结束。
ps：但是func3跟func4虽然都没问题。但是print 的⽅式并不同，func3输出5.3.2.1。但是func4的输出结果是1.2.3.4.5 因为他每次循环是没有⾛print就进⼊了下⼀个循环 之中，往外出的时候才会进⾏打印。
⼆、时间复杂度
类⽐⽣活中的⼀些事件，估计时间：
1.眨⼀下眼            ⼀瞬间/⼏毫秒
2.⼝算“29+68”            ⼏秒
3.烧⼀壶⽔            ⼏分钟
4.睡⼀觉            　⼏⼩时
5.完成⼀个项⽬          ⼏天/⼏星期/⼏个⽉
6.飞船从地铁飞出太阳系      ⼏年
时间复杂度的表⽰⽅式
1 print('Hello World')快速排序python实现
2 print('Hello Python')
3 print('Hello Algorithm')
4 #⽤时间复杂度来讲是O(1)
5
6 for i inrange(n):
7 print('Hello World')
8 for i inrange(n):
9 print('Hello World')10 #⽤时间复杂度来讲是O(n²)
11
12 for i inrange(n):13 for i inrange(n):14 print('Hello World')15 #⽤时间复杂度来讲是O(n²)
16
17 while n > 1:18 print(n)19 n = n // 2
20 #⽤时间复杂度来讲是O(logn)
时间复杂度-⼩结：
1.时间复杂度是⽤来估计算法运⾏事假你的⼀个式⼦(单位)。
2.⼀般来说，时间复杂度⾼的算法⽐复杂度低的算法慢。
3.常见的时间复杂度(按效率排序)
O(1)
4.不常见的时间复杂度(看看就好)
O(n!)  O(2^n)  O(n^n)
5.如何⼀眼判断时间复杂度？
循环减半的过程---O(logn)
⼏次循环就是n的⼏次⽅的复杂度
三、空间复杂度
1.空间复杂度：⽤来评估算法内存占⽤⼤⼩的⼀个式⼦
2.“空间换时间”
四、列表查：从列表中查指定元素
输⼊：列表、待查元素
输出：元素下标或未查到元素
顺序查：
从列表第⼀个元素开始，顺序进⾏搜索，直到到为⽌。
1 defordinary_lookup(number):
2 dict = range(1000)
3 for i indict:
4 if i ==number:
5 print(i)
6 break
7 ordinary_lookup(200)
⼆分查
从有序列表的候选区data[0:n]开始，通过对待查的值与候选区中间值的⽐较，可以使候选区减少⼀半。
1 importtime,random2
3 defcal_time(func):
4 def wrapper(*args,**kwargs):
5 ti =time.time()
6 x = func(*args,**kwargs)
7 ti2 =time.time()
8 print('time cost:',func.__name__,ti2-ti)
9 returnx10 returnwrapper11
12 @cal_time13 defbin_search(data_set,val):14 low =015 high = len(data_set) - 1
16 while low <=high:17 mid = (low + high)//2
18 if data_set[mid] ==val:19 returnmid20 elif data_set[mid] <21 low="mid">
22 else:23 high = mid - 1
24 return
25
26
27 def_binary_search(dataset, find_num):28 if len(dataset) > 1:29 mid = int(len(dataset) / 2)30 if dataset[mid] == find_num: #find it
31 #print("到数字", dataset[mid])
32 pass
33 elif dataset[mid] > find_num: #的数在mid左⾯
34 #print("\033[31;1m的数在mid[%s]左⾯\033[0m" % dataset[mid])
35 returnbinary_search(dataset[0:mid], find_num)36 else: #的数在mid右⾯
37 #print("\033[32;1m的数在mid[%s]右⾯\033[0m" % dataset[mid])
38 return binary_search(dataset[mid + 1:], find_num)39 else:40 if dataset[0] == find_num: #find it
41 #print("到数字啦", dataset[0])
42 pass
43 else:44 pass
45 #print("没的分了，要的数字[%s]不在列表⾥" % find_num)
46
47 @cal_time48 defbinary_search(data_set, val):49 return_binary_search(data_set, val)50 #不要在递归⾥⾯直接加装饰器会⽆限调⽤。
51 #循环要⽐递归有效率
52 #切⽚是⼀个特别耗费时间的操作
53
54 data = list(range(100000))55 bin_search(data,152)56 binary_search(data, 152)
练习：使⽤⼆分查法，进⾏查相应的id号码。
1 defrandom_list(n):
2 ids = list(range(1001,1001+n))
3 result =[]
4 a1 = ['周','x','x,'x','x','x','x','x','x']
5 a2 = ['杰','x','x','x','x','x','x','x']
6 a3 = ['伦','x','','','x','x','x','x','x','x']
7 for i inrange(n):
8 age = random.randint(18,60)
9 id =ids[i]10 name = random.choice(a1)+random.choice(a2)+random.choice(a3)11 name_dict = {'id':id,'name':name,'age':age}12
result.append(name_dict)13
14 returnresult15
16 #⽤于⽣成⼀个关于姓名的列表包含字典
17
18 defbin_search(val):19 data_set = random_list(10000)20 low =021 high = len(data_set) - 1
22 while low <=high:23 mid = (low + high)//2
24 if data_set[mid]['id'] ==val:25 returnmid26 elif data_set[mid]['id'] <27 low="mid">
28 else:29 high = mid - 1
30 return
31 print(bin_search(1160))32
33 #⽤⼆分查进⾏查⽣成列表内的id号在第⼏个
五、列表排序：将⽆序列表变为有序列表
1.应⽤场景：
各种榜单
各种表格
给⼆分排序⽤
给其他算法⽤
2.使⽤⽅式
输⼊：⽆序列表
输出：有序列表
分为⽣序和降序
3.排序low b 三⼈组：
冒泡排序
选择排序
插⼊排序
4.快速排序
5.排序NB两⼈组：
堆排序
归并排序
6.什么⼈⽤的排序
基数排序
希尔排序
桶排序
冒泡排序
⾸先，列表每两个相邻的数，如果前边的⽐后⾯的打，那么交换这两个数...
需要记住两个概念，趟,⽆序区。
时间复杂度：O(n²)
1 def bubble_sort(li):
2 for i in range(len(li)-1): #记录多少趟
3 flag =False
4 for j in range(0,len(li)-i-1): #交换了多少次
5 if li[j] > li[j+1]:
6 li[j],li[j+1] = li[j+1],li[j] #交换
7 flag =True
8 ifnot flag:
9 break
选择排序
⼀趟便利记录最⼩的数，放到第⼀个位置；
再⼀趟遍历记录剩余列表中最⼩的数，继续放置；
需要记住两个概念，⽆序区，最⼩数的位置。
时间复杂度：O(n²)
1 defselect_sort(li):
2 for i in range(len(li)-1):
3 min_loc =i
4 for j in range(i+1,len(li)):
5 if li[j]
插⼊排序
列表被分为有序区和⽆序区两个部分。最初有序区只有⼀个元素。
每次从⽆序区选择⼀个元素，插⼊到有序区的位置，直到⽆序区变空。
需要记住两个概念，摸到的牌,⼿⾥的牌。
时间复杂度：O(n²)
1 definsert_sort(li):
2 for i in range(1,len(li)):
3 tmp =li[i]
4 j = i - 1
5 while j>=0 and li[j] >tmp:
6 li[j+1] =li[j]
7 j = j - 1
8 li[j+1] = tmp
快速排序：快
写好的排序算法⾥最快的
快的排序算法⾥最好写的
时间复杂度：O(nlogn)
需要记住两个概念，整理，递归。
快排的思路：
1.取⼀个元素p(第⼀个元素)，使元素p归位；
2.列表被p分成两个部分，左边都⽐p⼩，右边都⽐p⼤；
3.递归完成排序。
1 defpartition(data,left,right):
2 tmp =data[left]
3 while left < right and left <
4 while data>=tmp:
5 right = right - 14>
6 data[left] =data[right]
7 while left < right and data[left] <=tmp:
8 left = left +1
9 data[right] =data[left]10 data[left]=tmp11 returnleft12
13 defquick_sort(data,left,right ):14 if left <15 mid="partition(data,left,right)16" quick_sort>
堆排序--树与⼆叉树简介
树是⼀种数据结构    ⽐如：⽬录结构
树是⼀种可以递归定义的数据结构
树是由n个节点组成的集合：
如果n=0，那这是⼀颗空树;
如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本⾝⼜是⼀棵树。
⼀些概念
根节点、叶⼦节点
树的深度(⾼度)
树的度
孩⼦节点/⽗节点
⼦树
特殊且常⽤的树--⼆叉树
⼆叉树：度不超过2的树(节点最多有两个叉)
两种特殊⼆叉树
满⼆叉树
完全⼆叉树
⼆叉树的存储⽅式

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。