斯坦福CS161算法分析与设计笔记

参考资料

• 【斯坦福大学】CS161 算法分析与设计（完结 · 中英字幕 · 机翻）

• 时刻问自己 Can we do better ?

Karatsuba Algorithm

也叫快速乘法算法，是对于大数的相乘的一种优化算法，是高斯复数乘法算法的推广

下面是一个简单的例子来快速理解它的基本思想，但是不是完整的算法

//对于四位数5678和1234，两者相乘
#include
#include
using namespace std;

int main(){

int x1 = 5678, x2 = 1234;  
int a = 56, b = 78, c = 12, d = 34;  

int step1 = a \* c;  
int step2 = b \* d;  
int step3 = (a + b)\* (c + d);  
int step4 = step3 - step2 - step1;  
int step5 = step1 \* pow(10,4) + step2 + step4 \* pow(10,2);  
cout << step1 << endl  
     << step2 << endl  
     << step3 << endl  
     << step4 << endl  
     << step5 << endl;  
cout << x1 \* x2 << endl;  
return 0;  

}
//结果一致
672
2652
6164
2840
7006652
7006652

Course Topics

• Vocabulary for design and analysis of algorithms
  • big-O
• Divide and conquer algorithm design paradigm
  • this is no one silver bullet in algorithm design
• Randomization in algorithm design
• primitives for reasoning about graphs
• Use and implementation of data structures

Topics in Sequel Course

• Greedy algorithm design paradigm
• dynamic programming algorithm design paradigm
• NP-complete problems and what to do about them
• Fast heuristics with provable guarantees
• Fast exact algorithms for special cases
• Exact algorithms that beat brute-force search

Skills you’ll lean

• Become a better programmer
• Sharpen your mathematical and analytical skills
• Start ‘’thinking algorithmically”
• Literacy with computer science’s “greatest hits”
• Ace your technical interviews

Merge Sort

Recursive Algorithm