一、程序 = 数据结构 + 算法

1. 数据结构
   1-1：逻辑结构
   集合结构、线性结构、树形结构、图形结构
   1-2：物理结构(存储结构)
   顺序存储、链式存储
2. 算法
   2-1：算法特点
   有穷性（通过有限次计算可以结束该程序）、确定性、可行性、输入、输出(至少一个输出)。
   2-2：算法设计要求
   正确性、可读性、健壮性、效率高与低存储量需求（例如女朋友干活勤快但是吃得少）
3. 时间复杂度
   高效率是指算法执行的时间短耗费的资源少。指程序运行的次数
   常用时间复杂度：
   (1)常数阶:O(1)
   (2)对数阶:O(log2 n)
   (3)线性阶:O(n)
   (4)线性对数阶:O(n log2 n)
   (5)平方阶:O(n^2^)
   (6)立方阶:O(n^3^)
   (7)k次方阶:O(n^k^)
   (8)指数阶:O(2^n^)
   n越大，时间复杂度越大。

4. 空间复杂度

   程序运行所消耗的存储空间

   时间复杂度攻略:

5. 用常数1取代运行时间中的所有的加法常数。
6. 在修改后的运行次数函数中，取最高阶项。
7. 如果最高项存在且不是1，则去除与这个项相乘的常数。（2*n^3+1======>时间复杂度T(n) = O(n^3)）

8. 得到的结果就是最大O阶。

   举个栗子

9. 常数阶：

int sum = 0,n = 100;printf("hello,");printf("I am Jakarta,");printf("today,we will study ");printf("data structure");sum = n/2;

这里输出的4句话与n无关，不管n是多少，输出都是四句话。根据攻略1得知：这里的时间复杂度T(n) = O(1);为常数阶。

1. 线性阶

int i,n=100,sum = 0;for(i=0;i

算法执行次数与n有关，所以这里T(n) = O(n);

1. 平方阶

int i,j,n = 100;for(i=0;i

这里双层循环，所以T(n) = O(n^2^); k层循环同理(n^k^)。

int i,j,n = 100;for(i=0;i

这里内层循环发生变化，具体解决方案如下：

时间复杂度从小到大排序：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2^) < O(n^3^) < O(2^n^) < O(n!) < O(n^n^)

本文参考小甲鱼老师的数据结构教程：