算法基础

article/2025/11/10 19:59:06

什么是算法？

算法（Algorithm）
是指解题方案的准确而完整的描述，
是一系列解决问题的清晰指令，
算法代表着用系统的方法描述解决问题的策略机制。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

大 O 表示法

定义：如果存在着正的常数 c 和自然数 n0，当 n >= n0 时；有 f (n) <= Cg(n) 成立，则称 f( n ) = O（g( n ))

算法分析中，如果一个的算法的时间复杂性是O(g( n ))，
读作 g( n ) “ 级 ” 的或 “ 阶 ” 的。
如：线性阶的(O(n))、平方阶的(O(n^2))、立方阶的(O(n^3)) ……

1) 加法规则 T(n,m) = T1(n) + T2(n) = O (max ( f(n), g(m) )
2) 乘法规则 T(n,m) = T1(n) * T2(m) = O (f(n) * g(m))
3) 一个特例（问题规模为常量的时间复杂度）
在大O表示法里面有一个特例，如果T1(n) ＝ O(c)， c是一个与n无关的任意常数，
T2(n) = O ( f(n) ) 则有T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) )
在大O表示法中，任何非0正常数都属于同一数量级，记为O(1)。
4) 一个经验规则
复杂度与时间效率的关系：
c < log2n < n < n*log2n < n2 < n3 < 2n < 3n < n! （c是常量）
高低

越靠左边效率越高，越靠右边效率越低

算出次数方程，求极限值

案例分析(一)
设 T(n) = (n+1)2 = n2+2n +1 <= n2 + 2n2 + n2;
选 n0 = 1, c=4 ; T(n) <= 4n2。所以，T(n) = O(n2) 当 n 为无穷大，4可以忽略
案例分析(二)
设 T(n) = 3n3+2n2
T(n) <= 5n3。所以，T(n) = O(n3)

在算法分析中，通常所说的找到了时间复杂性的级别，
是指找到了同样级别的最简单的函数。
如：307 n2、 n2/2、 n2 都是同一级别的函数，最简单的函数是n2 。
所以， 307 n2、 n2/2、 n2 的级别都是O(n2 ) 。

时间复杂性的级别的判断：级别越低越好

如果算法的空间和数据的数目个数无关，空间复杂度就是O(1)

常用排序算法复杂度

常用程序的时间复杂度

/*算法: 解决问题的方法特征:1.有穷性:有限个执行步骤,执行结束终止2.确切性: 每一步都有确定的含义3.输入项:0个或者多个 要有数据的输入 默认初始化的方式4.输出项:对输入的数据做实质性分析5.可行性:每一个步骤在一定时间内可以完成算法优劣:1.时间复杂度:程序运行的时间2.空间复杂度:程序用到的最大空间3.正确性4.可读性5.健壮性:针对特殊数据代码是否可行时间复杂度: 大O表示法用程序执行的最多的次数去描述时间复杂度放大化T(n)=n 次 ---> O(n);T(n)=2*n+n^2+1 次  2*n+n^2+1<=3*n^2  O(n^2) 近似描述T(n)=n^2+1 次  O(n^2);  极限T(n)+T(n^2) 次 Max(T(n),T(n^2))  O(n^2);T(n)=C(常量)   O(1);
*/
#include <stdio.h>
/*1.函数调用: O(1);2.交换数据: O(1);3.循环看循环条件No.1 循环条件是变量-> 时间复杂度跟随变量变化4.递归的复杂度递归操作:No.1 每次递归都是问题的规模的减半,其他地方是常数 二分法T(n)=T(n/2)+O(1)   T(n)=O(log2N)No.2 每次操作-1 递推的形式形成递归 T(n)=O(n)    求阶乘
*/
void test1(int n) 
{int x = 0;for (int i = 1; i <= n; i++) {x++;      //n}//时间复杂度为O(n)  最多执行n次     for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {x++;  //n^2}}//时间复杂度为O(n^2) 最多执行n^2次     //加法原则Max()
}
void test0(int n) 
{
#if 0//O(n);int result = 0;for (int i = 0; i < n; i++)result += i;printf("%d\n", result);
#endif//O(1);-> 数学表达式 等差数列求和int result = 0;result = n * (n + 1) / 2;//1+2+3+..n;//n+n-1+..1;//(n+1)n/2printf("%d\n", result);
}
int  F(int n) 
{if (n == 1 || n == 2)       //O(1)return 1;return F(n - 2) + F(n - 1); //O(n)
}int main() 
{int array[3] = { 1,2,3 };		//数组遍历-> 程序执行次数与数组长度有关联for (int i = 0; i < 3; i++) {printf("%d\t", array[i]);   //3次  无限化 n次}return 0;
}

一些简单的算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//字符串转数字
int my_atoi(char* str)			//123
{int result = 0;		int i = 0;while (str[i] != '\0')	    //1							//2      //3{result = result * 10 + str[i] - '0';   //result=1   10+2=12  //120+3//'1'-'0' =1  ASCIIi++;                    //位数}return result;
}
//递归的方式 要描述次数-> 加一个长度
int loop_atoi(char* str, int len) 
{if (len == 1)return str[len - 1] - '0';elsereturn loop_atoi(str, len - 1) * 10 + str[len - 1] - '0';
}//求最大公约数: 同时能够整除的两个数的最大整数
//链表的反转
//--->4 8  -->4 最大公约数
//--->2 3  -->6 最小公倍数
//递归的方式
int gcd(int m, int n) 
{//保持m是最大的if (m < n) {int temp = m;m = n;n = temp;}if (n == 0) {return m;       //直接返回m}return gcd(n, m % n);
}
//数字类的递归->把值带进去
unsigned int Gcd(unsigned int M, unsigned int N)
{unsigned int Rem;   //36 16      -->4while (N > 0){Rem = M % N;    //Rem=36%16  -->4   Rem=16%4=0M = N;          //M=16       -->    M=4N = Rem;		//N=4        -->    N=0}return M;			//4
}
int main() 
{printf("%d\t", my_atoi("1234"));printf("%d\t", loop_atoi("1234",4));printf("%d\t", gcd(8, 4));return 0;
}/*输出*/4