算法初识-时间复杂度空间复杂度

注：观看Adbul Bari算法视频

算法概念

 算法：先验分析，不依托于硬件，无语言限制，逻辑。
 程序：后验测试，依托硬件，语言限制，实现。

特点：

• 输入-0或多个
• 输出-至少一个
• 确定性-人能理解
• 有限性-有限集，时间集，必须有停止的时候
• 有效性-没必要的语句不要写

准则：

1. 时间：要高效-时间函数    f(n)=n  每行语句占一个单位时间
2. 空间：占用内存                s(n)=n  每个参数占一个字
3. 数据传输，宽带消耗（有必要传输很多数据吗，有优化空间吗）
4. 设备消耗的功率
5. CPU寄存器的消耗

频率计数法

1.一维数组之和
f(n) = 2n+3    s(n) = n+3     时间和空间复杂度都是O(n)

s=0                  ---1
for(i=0;i<n;i++){    --- 1,n+1,ns=s+A[i];         --- n
}
return s;            --- 1
s,i,n,A[i]           --- 1,1,1,n

2.二维数组之和
f(n) = 2n²+2n+1    s(n) = 3n²+3    时间和空间都是O(n²)

for(i=0;i<n;i++){               ---n+1for(j=0;j<n;j++){            ---nx(n+1)C[i,j] = A[i,j]+B[i,j];   ---nxn}
}
C,B,A,i,j,n                     ---nxn,nxn,nxn,1,1,1

3.二维矩阵之积
f(n) = 2n³+2n²+2n+1    s(n) = 3n²+4     时间复杂度O(n³)，空间复杂度O(n²)

for(i=0;i<n;i++){for(j=0;j<n;j++){for(k=0;k<n;k++){C[i,j] = C[i,j] + A[i,k]*B[k,j];}}
}

4.总结规律：只关心循环里面的语句执行多少次，只关心最高次方！（因为是加法，并不会叠加次方，所以只关心循环里面就可以。换句话说只关心最高次方的那一条语句就可以）

时间函数的追踪分析法(举例)

for循环为例

例1：

例2：
例3：


例4：
例5：
例6：
总结：i自增或自减的情况都是O(n)；i是乘法或者除法自增或自减的情况都是O(logn)；其余情况用追踪分析法。

while循环为例

while循环一定要分析，规律性较小

渐进符号

定义

三种渐进符号随便用哪个都可以，但是在用O和omega时，尽量使用接近theta否则没有意义！

函数比较方法

1.可以直接带入数值，来直观的看出谁大谁小（用很大数值代入会更直观）
2.可以用log比较法

应用

函数的best/worst/avg情况

这种最好最坏情况无论使用哪种渐进符号都可以，函数的好坏情况不取决于渐进符号，渐进符号只是个表示方式而已。
一般平均情况接近于最坏情况。

二叉搜索树特点：左边的元素小于右边的元素。普通二叉树就是无序的。
其中关于w(n)=树高，minW(n) = logn,maxW(n)=n

任何形式的数据都可以通过寻找/合并形成二叉搜索树以此来看时间复杂度