Coursera上斯坦福的算法课。为了提升英语水平特地去听的全英版的，可能需要适应一段时间。用的教材是 Algorithms Illuminated。上课讲的东西几乎和教材一致。课上有不懂的东西就直接去逼站搜机翻的视频或者看教材。
第一节课是导入，讲了Karatsuba的大数相乘的算法，和Merge sort（递归排序），以及大欧，西塔，欧米噶这些符号。后三个符号在学校的数据结构课上老师有讲过。但毕竟不是计算机专业，老师讲的没这么深入，只是停留在“感性”认识的阶段。这门课中的定义方法有点数学分析的感觉。很舒服~
相应笔记和python代码实现如下：
Karatsuba： 其实感觉挺鸡肋的。主要是思想。 因为python内部的算法也非常牛逼。直接把这两个大数相乘瞬间出结果。 甚至用time库计时的结果是0。 用定义Karatsuba函数进行相乘其实是更慢的… def str_minus(a,b): #时间复杂度为n tw = 0 k = len(a) - 1 outstr = "" for i in range(1,len(b)+1): if (eval(a[k]) - eval(b[len(b)-i]) - tw) < 0 : outstr = str(10 + eval(a[k]) - eval(b[len(b)-i]) - tw) + outstr tw = 1 else: outstr = str(eval(a[k]) - eval(b[len(b)-i]) - tw) + outstr tw = 0 k = k - 1 j = 0 for i in range(len(b), len(a)): #多余位数的计算。 k = len(a) - i - 1 if eval(a[k]) - tw < 0: outstr = str(10 + eval(a[k]) - tw) + outstr tw = 1 else: outstr = str(eval(a[k]) - tw) + outstr tw = 0 return outstr def str_plus(a,b): if len(a) > len(b): for i in range(len(b), len(a)): b = "0" + b else: for i in range(len(a), len(b)): a = "0" + a jw = 0 k1 = len(a) k2 = len(b) outstr = "" for i in range(1,k1+1): if (eval(b[k2-i]) + eval(a[k1-i]) + jw < 10): outstr = str(eval(b[k2-i]) + eval(a[k1-i]) + jw ) + outstr jw = 0 else: outstr = str(eval(b[k2 - i]) + eval(a[k1 - i]) + jw)[1] + outstr jw = 1 if jw: outstr = "1" + outstr if len(outstr) > len(a): for i in range(len(outstr),2*len(a)): outstr = "0" + outstr return outstr def kara(x,y): if len(x) > len(y): for i in range(len(y),len(x)): y = "0" + y else: for i in range(len(x),len(y)): x = "0" + x n = len(x)//2 #默认x，y等长。并且是2的幂级数 a = x[0:n] b = x[n:] c = y[0:n] d = y[n:] if (len(a) != 1) and (len(b) != 1) and (len(c) != 1) and (len(d) != 1): result_ac = kara(a,c) result_bd = kara(b,d) o1 = kara(str_plus(a,b),str_plus(c,d)) result_mid = str_minus(str_minus(o1,result_bd),result_ac) op = str_plus(str_plus(result_ac + 2*n*"0",result_mid + n*"0"),result_bd) return op else: op = str(100 * (eval(a) * eval(c)) + 10 * (eval(a) * eval(d) + eval(b) * eval(c)) + eval(b) * eval(d)) if len(op) != 4: for i in range(4 - len(op)): op = "0" + op return op print(kara("3141592653589793238462643383279502884197169399375105820974944592","2718281828459045235360287471352662497757247093699959574966967627")) print(str(3141592653589793238462643383279502884197169399375105820974944592*2718281828459045235360287471352662497757247093699959574966967627))
结果为：8.539733754338333e+126
Merge sort： 因为python里有自带的sorted方法，，所以其实这个也没啥卵用。但在C里可能会很有用。
def ms(ls): n = len(ls) if n != 1: ls_1 = ms(ls[0:n // 2]) ls_2 = ms(ls[n // 2:]) s_ls = [] ls_1.append(9999) ls_2.append(9999) i = 0 j = 0 for k in range(n): if ls_1[i] < ls_2[j]: s_ls.append(ls_1[i]) i = i+1 else: s_ls.append(ls_2[j]) j = j+1 return s_ls else: return ls ls = [2,5,346,457,5,8,35,2435,7,5,86,5] print(ms(ls))下面是从别的地方抄过来的C++的递归排序代码。
#include<iostream> using namespace std; void merging(int*a,int head,int mid,int tail) { int len=tail-head+1,i=head,j=mid+1,index=0; int temp[len]={};//临时数组 while(i<=mid&&j<=tail) { if(a[i]<=a[j]) temp[index++]=a[i++]; else temp[index++]=a[j++]; } while(i<=mid) temp[index++]=a[i++]; while(j<=tail) temp[index++]=a[j++]; for(int i=0;i<len;i++) a[head+i]=temp[i]; } void merge_sort(int*a,int head,int tail) { if(head<tail)//当head<tail说明是多个数据一组,就继续拆分 //而当head=tail说明一个数据一组了,就返回开始合并 { int mid=(head+tail)/2; merge_sort(a,head,mid);//拆分左半部 merge_sort(a,mid+1,tail);//拆分左半部 merging(a,head,mid,tail);//合并两部分 } } int main() { int a[]={9,1,2,8,5,3,7,4,6}; merge_sort(a,0,8); for(int i=0;i<9;i++) cout<<a[i]<<" "; cout<<endl; return 0; }来源： https://blog.csdn.net/qq_40930559/article/details/104190984?ops_request_misc=%7B%22request%5Fid%22%3A%22160188448719725255563051%22%2C%22scm%22%3A%2220140713.130102334…%22%7D&request_id=160188448719725255563051&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduend~default-3-104190984.first_rank_ecpm_v3_pc_rank_v2&utm_term=递归排序c&spm=1018.2118.3001.4187
