--------------------------------
Author ： ShawnDong
updateDate ：2019.5.31
Blog ： ShawnDong98.github.io
--------------------------------
绪论
程序 = 数据结构 + 算法
物理结构：顺序存储结构和链式存储结构
逻辑结构：线性结构(顺序表、链表)和非线性结构(树、图)
算法的特性： 输入、输出、有穷性、确定性、可行性
算法设计的要求：正确性、可读性、健壮性、时间效率高和存储量低
时间复杂度和空间复杂度
时间复杂度
推导大O阶方法
- 用常数1取代运行时间中所有的加法常数
- 修改后的运行次数函数中，只保留最高项
- 如果最高项存在且不是1，则去除与这个项相乘的常数
- 得到最后的结果就是大O阶
线性阶
一般含有非嵌套循环涉及线性阶，线性阶就是随着问题规模n的扩大，对应计算次数呈直线增长
int i, n = 100, sum = 0;
for(i=0; i<n; i++){
sum = sum + i;
}
平方阶
int i, j, n = 100, sum = 0;
for(i=0; i<n; i++){
for(j=0; i<n; i++){
printf("I'm here...\n");
}
}
int i, j, n = 100, sum = 0;
for(i=0; i<n; i++){
for(j=i; i<n; i++){
printf("I'm here...\n");
}
}
由于当i=0时，内循环执行了n次，当i=1时，内循环执行了n-1次...当i=n-1时，内循环执行1次，所以总的执行次数应该是：
用推导大O的攻略，第一条忽略，因为没有常数相加。第二条只保留最高项，所以n/2这项去掉。第三条，去除与最高项相乘的常数，最终得到
对数阶
int i = 1, n = 100;
while(i<n){
i = i * 2;
}
- 由于每次i*2之后，就举例n更近一步，假设有x个2相乘后大于或等于n，则会退出循环。
- 于是由
得到
， 所以这个循环的时间复杂度为
)
函数调用的时间复杂度分析
void function(int count){
printf("%d", count);
}
int main(){
int n=0, i=0, j=0;
n++; //1
function(n); //n
for(i=0; i<n; i++){ //n^2
function(i);
}
for(i=0; i<n; i++){ //n^2
for(j=i; j<n; j++){
printf("%d", j);
}
}
}
常见的时间复杂度
常见的时间复杂度
常用的时间复杂度所耗费的时间从小到大依次是：
