|
|
什么是数据结构？
就是一组能组再一起的集合对象。比如数组、链表、队列等。
什么是算法？
就是解决问题的
1、算法的特性
1.1 五个特征
有穷性、确定性、可行性、有输入、有输出
while(true){}//死循环，不是算法1.2 设计原则
正确性、可读性、健壮性（bug）：写出的代码很少有bug，且系统比较稳定
高效率与低存储：内存+CPU（内存占用最小，CPU占用最小，运算速度最快）
1.3 评价算法的两个总要指标：时间复杂度和空间复杂度
时间复杂度：运行一个程序所花费的时间，O()表示
空间复杂度：运行程序所需要的内存（尽可能避免出现OOM（内存溢出））
2、时间复杂度分析
2.1 时间复杂度表示方法：大O表示法
O(1),O(n),O(logn),O(nlogn),O(n^2),O(2^n)
2.2 时间复杂度如何分析
（1）找for、while、递归，而且要找循环量大的那一段
（2）有网络请求的地方（http，rpc远程调用，数据库请求）
就是测试时间：打印log，计算平均时间
2.3 复杂度比较：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)
2.4 时间复杂度分析
计算时间复杂度 往往是计算比较大的 而且是不确定的数，如果已经确定了，那么就不用计算了，也是我们说的常量。
常数级O(1)
#include<stdio.h>
int main(){
for(int i=0;i<9;i++){ //时间复杂度为O(1);对于已知的都为常量1，未知的才需要计算复杂度
i = i + 1;
}
printf(&#34;Hello World&#34;); //执行一次
return 0; //执行一次
}对数级O(logn)
#include<stdio.h>
int main(){
int i=1,n=10000; //执行一次
while(i<=n){ //执行logn次
i*=2;
}
return 0; //执行一次
}
//i的值：2 4 8 16 32,=》2^0,2^1,2^2,2^3,.....2^n
//===> 2^x=n =>求出x就是我们运行的次数 => x=log2n =>计算机忽略掉常数 => x = logn =>O(logn)
//二分查找 为什么是logn的算法？
//1~100 找69这个数
//50:(1+100)/2 = 50线性对数级O(nlogn)
#include<stdio.h>
int main(){
int n=10000,ans=0; //执行一次
for(int i=0;i<n;i++){ //执行n次
int j=0; //执行1次
while(j<=n){ //执行log(n)次
j*=2;
}
}
return 0; //执行一次
}线性级O(n)
#include<stdio.h>
int main(){
int n=10000,ans=0; //执行一次
for(int i=0;i<n;i++){ //运行了多少次？O(n) n一定是一个未知的，如果n是已知6的，则是O(1)
ans+=i; //执行一次
}
return 0; //执行一次
}平方级别O(n^2）
#include<stdio.h>
int main(){
int n=10000,ans=0; //执行一次
for(int i=0;i<n;i++){ //执行n次
for(int j=0;j<n;j++){ //执行n次
ans+=j;
}
}
return 0; //执行一次
}
//运行了多少次？O(n^2)n*(n+1)/2 => O(n^2); => (n^2+n)/2
//注意有个规律，有加减法的时候，找次数最高的那个
指数级O(2^n)
long aFunc(int n) { //运行多少次？
if (n <= 1) {
return 1;
} else {
return aFunc(n - 1) + aFunc(n - 2);
}
}
//运行次数T(0)=T(1)=1,同时T(n)=T(n-1)+T(n-2)+1，1是其中的加法算一次执行
//显然T(n)=T(n-1)+T(n-2)是斐波那契数列，通过归纳证明法可以证明,
//当n>=1 时，T(n)<(5/3)^n,同时n>4时T(n)>=(3/2)^n,
//所以该方法的时间复杂度可以表示为O(5/3)^n，简化后为O(2^n)3、空间复杂度分析
如何查找空间复杂度？
（1）找花了内存的地方。数据
（2）找开了空间的地方，比如数组、链表、缓存对象（map）、递归
总结
学了时间复杂度，那我们的目的就是要把代码写到最优，效率最高
效率有高到低：O(1) > O(logn) > O(n) >O(nlogn) >O(n^2) >O(n^3)
比如排序，冒泡算法的时间复杂度是O(n^2)=>找更优秀的排序算法：快速排序、归并排序、堆排序
优化的目标就是要往O(1)靠近 |
|
发表于 2022-11-26 20:45:30