数据结构（一）

第一章算法

1.1 算法的时间复杂度

时间复杂度的定义：
（1）时间复杂度表示为O(f(n))，随问题规模n的逐渐增大，算法时间的增长率和f(n)相同
（2）O(1)：常数阶
（3）O(n)：线性阶
（4）O((n^2))：平方介
（5）O((log_2n))：对数阶
```
while(count < n){
    //每次循环，count都会离n进一步，需要循环对数次
    count = count*2;
}
```
推到O阶的方法
（1）用常数1取代运行时的所有加法
（2）修改后的运行次数函数中，只保留最高阶
（3）如果最高阶存在且不是1，则去除这个项相乘的常数。
上面三部得到的结果就是O的阶
（4）eg：如下例子的复杂度
当i=0时，内循环执行了n次；当n=1时，执行了n-1次，所以总次数为n+(n-1)+(n-2)+...+1 = (frac{1}{2}n^2+frac{1}{2}n) 。因此时间复杂度为O((n^2))
```
for(int i=0;i<n;i++){
    for(j=i;j<n;j++){
        /* 事件复杂度为O(1)的程序步骤  */
    }
}
```

（5）又一个例子
操作总次数=1+1+(frac{n(n+1)}{2}),所以时间复杂度为O((n^2))
c n++; /* 执行次数为1 */ fun(n); /* 执行次数为1 */ for(int i=0;i<n;i++){ /* 执行次数为如上面的例子 */ for(int j=i;j<n;j++){ /*时间复杂度为O(1)的操作*/ } }

1.2 常用事件复杂度的比较

时间复杂度公式
(O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n!) < O(n^n))

第一章 算法

1.1 算法的时间复杂度

1.2 常用事件复杂度的比较

相关推荐

第一章算法