什么是算法?当我第一次接触到这个东西的时候,我产生了疑问。
其实算法就是解决问题的方法:
- 问题是什么?
- 我们有什么?
- 我们想得到什么?
- 尝试最简单的方式解决
- 看看如何改进
当我们在尝试写算法的时候,我们可能考虑到算法的效率问题,这个算法是否在不同情况都能保证它的效率,所以我们要对自己写出的算法有一个评估。
关于描述一个算法的复杂度,我们有下面这个图。
增长顺序:
- O(1)
- O(logn)
- O(n)
- O(nlogn)
- O(n^2)
- O(2^n)

随着输入越来越大,算法所运算的时间也会发生变化;用空间复杂度,时间复杂度来衡量一个算法。
注意:以下我们只考虑时间复杂度。
O(1):
def square(x):
return x * x
square(3)
O(n):
def find_max(l):
if l == None:
return None
mx = l[0]
for n in l:
if n > mx:
mx = n
return mx
O(n^2):
def has_duplicate(l):
for i in range(len(l)):
for j in range(i + 1, len(l)):
if l[i] == l[j]:
return True
else:
return False
— Fibonacci:
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
这个使用递归来求斐波拉契数列时间复杂度为 O(n^2),因为再最后 return f(n-1) + f(n-2),两个递归调用内有重复计算的地方。例如 n = 6,则递归为 fi(5) + f(4),前一项递归为 f(4) + f(3);后一项 f(3) + f(2)这样下去......,你会发现 f(4) 计算了2次,f(3) 计算了3次......,到最后你发现 f(1) 计算了7次。
改进版的算法(让其不用重复计算):
def fibonacci2(n):
assert(n>=0)
if (n <= 1):
return (n,0)
(a, b) = fibonacci3(n-1)
return (a+b, a)
— Binary Search(a sorted list)
- Solution 1: Brute Force(匹配法):
def search(num_list, val):
if num_list == None:
return -1
for i in range(0, len(num_list)):
if (num_list[i] == val):
return i
return -1
- Solution 2: Binary Search (递归法):
def bi_serach_re(num_list, val):
def bi_search(l, h):
if l > h:
return -1
mid = (l + h) // 2
if (num_list[mid] == val):
return mid;
elif (num_list[mid] < val):
return bi_search(mid + 1, h)
else:
return bi_search(l, mid - 1)
return bi_search(0, len(num_list))
- Solution 3: Binary Search (分治法):
def bi_search_iter(num_list, val):
l = 0
h = len(num_list)
while (l <= h):
mid = (l + h) // 2
if (num_list[mid] == val):
return mid
elif (num_list[mid] < val):
l = mid + 1
else:
h = mid - 1
return -1
Solution 2,3都是O(nlogn),将数据查找时间都大大缩短了;例如:1—100里猜数的游戏,我们先猜50,这会让空间减半,下一次继续这样猜可以快速锁定。如果是1—100000,会猜多少次呢?
— Sorting
- Bubble sort(冒泡算法)
例如 [6, 3, 1, 5, 4, 4] 这样一个数列,相邻两个数比较,如果是前一个大于后一个则交换,所以得到第一个Pass:[3, 1, 5, 4, 3, 6](此时6已经排好序了,循环了6次),第二个Pass是 [1, 3, 4, 2, 5, 6](此时5、6已经排好序了,循环了5次),第三个Pass是 [1, 3, 2, 4, 5, 6](此时4、5、6已经排好序了,循环了5次),第四个Pass是 [1, 2, 3, 4, 5, 6](此时3、4、5、6已经排好序了,循环了5次),第五个Pass(不变)是 [1, 2, 3, 4, 5, 6](此时2、3、4、5、6已经排好序了,循环了5次),第六个Pass(不变)是 [1, 2, 3, 4, 5, 6](此时1、2、3、4、5、6已经排好序了,循环了5次)。
按照这样的思路我们可以得到:
def _bubble_sort(nums: list, reverse=False):
import time
start = time.time()
for i in range(len(nums)):
for j in range(len(nums) - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
if reverse:
nums.reverse()
t = time.time() - start
return len(nums), t
def bubble_sorted(nums: list, reverse=False) -> list:
"""Bubble Sort"""
nums_copy = list(nums)
_bubble_sort(nums_copy, reverse=reverse)
return nums_copy
l = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
l = bubble_sorted(l, reverse=True)
print(l)
- Insert sort(插入算法):
例如 [3, 8, 2, 1, 7, 6, 5] 这样一个list,Pass1:前两个数比较顺序不变,Pass2:第二个和第三个数字比较交换位置 ([3, 2, 8, 1, 7, 6, 5]),‘2‘再与’3‘交换,这样使得前三项都为sorted了 ([2, 3, 8, 1, 7, 6, 5]),Pass3:’1‘和前面的已经sorted的数再进行插入比较 ([1, 2, 3, 8, 7, 6, 5])……
def insert_sort(items):
for sort_inx in range(1,len(items)):
unsort_inx = sort_inx
while unsort_inx > 0 and items[unsort_inx-1] > items[unsort_inx]:
items[unsort_inx-1], items[unsort_inx] = items[unsort_inx], items[unsort_inx-1]
unsort_inx = unsort_inx-1
return len(items)
这个的时间复杂度是O(n^2)
- Selsecion sort(选择算法):
例如 [3, 8, 4, 2, 1, 6] 这样一个list,先找这个list的最小的index (以下简称minIdx),这个minIdx=4,然后把第一个3和它交换位置 (pass1: [1, 8, 4, 2, 3, 6]),再找新的 minIdx=3,和第二个8交换位置 (pass1: [1, 2, 4, 8, 3, 6])……
def sort1(array):
for i in range(len(array)):
pos_min = i
for j in range(i + 1,len(array)):
if (array[j] < array[pos_min]):
pos_min = j
array[i],array[pos_min] = array[pos_min],array[i]
return array
就类似这样去实现这个算法,这个比较简单(O(n^2)的复杂度
- Merge sort(合并算法):
这个是令我非常头疼的算法,随便给你一个数组[3, 9, 6, 5, 8, 2, 4, 7],我们先要利用分治法(DIvide and conque)进行拆分,[3, 9] [6, 5] [8, 2] [4, 7],然后每组进行sort,得到[3, 9] [5, 6] [2, 8] [4, 7],左边两个进行Merge,右边两个进行Merge,然后得到[3, 5, 6, 9] [2, 4, 7, 8],然后这个两个在进行大Merge,最终得到排好序的list。
这个Merge是如何实现的呢?
把 [3, 5, 6, 9] 设为 a[i] ,i 指向第一个数字
把 [2, 4, 7, 8] 设为 b[j] ,j 指向第一个数字
a[0] > b[0],则把 b[0] append 到一个空 list 中去,然后 j+1;
a[0] < b[1],则把 a[0] append 到上一个 list 中去,然后 i+1;
……
最后得到 [2, 3, 4, 5, 6, 7, 8, 9]
★注意:当i走到头了,j后面还有数字;也有可能j走到头了,i后面还有数字;这个时候就应该把多余的数字加到那个list后面。
所以我们写出了下面的代码:
def _merge(a: list, b: list) -> list:
"""Merge two sorted list"""
c = []
while len(a) > 0 and len(b) > 0:
if a[0] < b[0]:
c.append(a[0])
a.remove(a[0])
else:
c.append(b[0])
b.remove(b[0])
if len(a) == 0:
c += b
else:
c += a
return c
def _merge_sorted(nums: list) -> list:
if len(nums) <= 1:
return nums
m = len(nums) // 2
a = _merge_sorted(nums[:m])
b = _merge_sorted(nums[m:])
return _merge(a, b)
def merge_sorted(nums: list, reverse=False) -> list:
import time
start = time.time()
"""Merge Sort"""
nums = _merge_sorted(nums)
if reverse:
nums = nums[::-1]
t = time.time() - start
return nums, len(nums), t
关于Sort就说到这里,剩下还有Quick Sort以及搜索算法将在在平坦的算法路上懵逼地曲折前进(二)上和大家讨论。

Qicloud
2020-01-01 14:10:22来催更了
卷土
2020-01-02 21:26:14@Qicloud 刚刚修复了评论邮件系统,文章应该会过几天
晴和君
2019-12-26 22:02:38当年学得一脸懵逼
卷土
2019-12-31 23:30:11@晴和君 哈哈哈
rares
2019-12-01 18:28:03听阿里某牛同学经常说某某某人算法很牛
卷土
2019-12-08 11:22:04@rares 哈哈哈,某牛同学
姜辰
2019-11-27 10:36:05一脸懵逼的进来,然后出去。
卷土
2019-12-08 11:21:37@姜辰 然后再进来
一间生活
2019-11-26 10:03:42在懵逼的阅读观看后懵逼地留下评论
卷土
2019-12-08 11:21:20@一间生活 我也开始懵逼了