参考资料

Karatsuba Algorithm

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

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

//对于四位数5678和1234，两者相乘
#include<iostream>
#include<cmath>
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