c语言的算法总结（算法基础C语言描述）
c语言的算法总结（算法基础C语言描述）void hello(int n){ int a b c; if(n>1){ hello(n-1); } printf("%d\n" n) } S(n) = O(n)每次递归调用，都会为方法开辟一块内存空间，虽然每块内存空间中都有a b c三个整数，但是他们与问题规模没有关系，所以空间复杂度为O(n) // n 占 4个字节 void hello(int n){ //flag占4n²个字节 int flag[n][n]; //temp占4n个字节 int temp[n]; //i占4个字节 int i; } S(n) = 4 4n² 4n 4 =
- 算法是为了解决问题需要遵守、被明确指定的指令的集合。
- 很多人说程序的本质是算法，就是因为程序的本质也是为了解决问题而使用的需要遵守、被明确指定的指令的集合。
- 如果一个算法是可行的，我们接下来要考虑的往往是算法的效率。比如说如果一个算法虽然可以解决问题，但是却要耗费很长的时间或不合理的内存空间，那这种算法其实也意义不大。
- 大O表示法
/*
* 这是一个简单的单循环算法
* n 表示循环的规模 =〉问题规模
*/
void hello(int n){
int i = 1;
//用 i 表示其与 n 的关系为 i<=n
while(i<=n){
printf("你叫什么名字？你玩过吃鸡吗？\n" i);
i ;
}
printf("废话，I'm a box on the ground");
}
- 假设 n 为 100，可以得到一个表达式为:T(100) = 1 101 2 * 100 1其中 T 表示单位时间成本 n 表示问题规模 T(n) = 时间复杂度第一个常数 1 表示 int i = 1;在程序中执行的次数。第二个常数 101 表示 while 判断执行的次数。后面依次类推.....最终得到一个详细的算法时间开销
- 我想我已经可是使用上述方法去计算算法时间复杂度了，但是现在我遇到了一个问题：我可能需要写一段很长很长的代码，如果我还用这种逐行去数的方式去计算实在显得有点不切实际。所以现在我的脑袋里浮现出了两个问题。如果一个算法有上千行的代码，难不成我也要一行一行地去数？我是否可以忽略某些部分，只关注代码中影响时间复杂度的最重要部分？
- 能！首先我们将 T(100) 中的 100 仍然使用代数 n(表示规模) ，可得 1 101 2 * 100 1 = 3n 3，对于程序而言，运算阶数低的部分的时间开销往往可以忽略不计，只保留阶数最高的部分（好读书不求甚解，可以先这么理解），于是乎哈哈得到 3n，最后还是由于好读书不求甚解的原因，当 n 变得足够大时，常数项往往可以忽略不计，遂得到 3n = n最后用大O表示法得到当前算法的时间复杂度为 T(n) = O(n)
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
常 < 对 < 幂 < 指 < 阶
- 嵌套循环
/*
* 这是一个简单的嵌套循环算法
* n 表示循环的规模 =〉问题规模
*/
void hello(int n){
int i = 1;
//用 i 表示其与 n 的关系为 i<=n
while(i<=n){
printf("你叫什么名字？你玩过吃鸡吗？\n" i);
i ;
//内层循环次数以及循环几轮取决于 n 的值，所以共执行n²次
for(int j = 0; j < n; j ){
printf("如果你玩吃鸡的话，我们可以组团吃鸡。\n");
}
}
printf("废话，I'm a box on the ground");
得到 T(n) = O(n) O(n²) 取最高阶的部分得出 T(n) = O(n²)
- 单次循环、 i 倍次递增
/*
* 这是一个简单的循环算法
* n 表示循环的规模 =〉问题规模
*/
void hello(int n){
int i = 1;
//用 i 表示其与 n 的关系为 i<=n
while(i<=n){
printf("你叫什么名字？你玩过吃鸡吗？\n" i);
i = i * 2;
}
printf("废话，I'm a box on the ground");
}
得到 T(n) = O(log2n)
log2n： 假设 n = 8 8的对数为3 ，2³ = 8。由于2³ 1 > 8，所以循环退出，最终循环一共执行了 3 次，3 = log2(8)，结果 T(n) = log2n
- 遍历查找算法
/*
* 这是一个简单的遍历查询算法
* n 表示循环的规模 =〉问题规模
*/
void hello(int flag[] int n){
int i = 0;
printf('find n\n')
//用 i 表示其与 n 的关系为 i<=n
while(i<n){
if(flag[i]==n){
printf("find it，厉害，值：%d\n" flag[i]);
break;
}
i ;
}
}
最好的情况：数组中第一个元素就是要查找的值 T(n) = O(1) 一般不采用
最坏的情况：数组中最后一个元素才是目标元素 T(n) = O(n)
平均情况：假设n在任意一个位置的概率相同 T(n) = O(n)
* 平均情况复杂度计算公式
* 循环次数x = (1 2 3 4 ... n) * 1/n = (n(1 n)/2)*1/n = 1 n/2
* T(n) = O(x) = O(n)
空间与问题规模的关系
示例- 循环递增
void hello(int n){
int i = 1;
while(i<=n){
printf("你见过凌晨4点的洛杉矶吗？%d\n" i);
i ;
}
printf("我没见过，但是我见过凌晨4点网吧，凌晨4点烧烤摊，还有凌晨四点的召唤师峡谷\n");
}
i&n都是内存中固定的常量，所以无论程序执行时i怎样变化，原地工作，复杂度都为O(1)
S(n) = O(1)
- 单个数组
// n 占 4个字节
void hello(int n){
//flag占4n个字节
int flag[n];
//i占4个字节
int i;
}
变量占用的空间相加 S(n) = 4 4n 4 = 4n 8 = O(n)
- 二维数组
// n 占 4个字节
void hello(int n){
//flag占4n²个字节
int flag[n][n];
//temp占4n个字节
int temp[n];
//i占4个字节
int i;
}
S(n) = 4 4n² 4n 4 = 4n² 4n = O(n²)
取最高阶 4n²
- 递归
void hello(int n){
int a b c;
if(n>1){
hello(n-1);
}
printf("%d\n" n)
}
S(n) = O(n)
每次递归调用，都会为方法开辟一块内存空间，虽然每块内存空间中都有a b c三个整数，但是他们与问题规模没有关系，所以空间复杂度为O(n)
- 递归&数组
void hello(int n){
int flag[n];
if(n>1){
hello(n-1);
}
printf("%d\n" n)
}
与上面相反，此处会有一个与问题规模关联的数组，所以代入一个等差数列 1 2 3 ... n = n(1 n)/2 = 1/2 * n² 1/2 * n
忽略常数项，取最高阶可得 T(n) = S(n²)
