数据结构与算法分析（1）——基础知识

M小白的学习笔记 17/11/30

1.数学基础

• 指数对数幂的运算
• 直接证明、反证法、数学归纳法
• 递归与迭代

2. 复杂度分析

P与NP
P：一类问题可以有算法在多项式时间求解。
NP： 没有已知算法在多项式时间求解，但是可以用多 项式时间验证一个答案是否其解

复杂度
RAM模型

C语言中使用clock()

clock_t start_time, end_time;
start_time = clock (); 
……//运算
end_time = clock (); 
printf ("%f \n", ((double)(end_time - start_time)/CLOCKS_PER_SEC));

典型例题

• 求最大公约数
• 折半查找
• 插入排序
• 最大子数列
• 求幂

分治思想