多个实现同一功能的算法，在相同情况下，运行时间越短，说明该算法效率越高。而影响算法运行时间的关键因素就是该算法基础操作的执行次数，基础操作的次数越少，算法的运行时间就越短。(基础操作，可以认为是该种计算机语言中无法再拆解的操作，例如：加一个数、减一个数、乘一个数、除一个数。)

算法1：总共执行 2n+3 次基础操作

void algorithm1(int n)// 算法1：总共执行 2n+3 次基础操作
{
	int i=0, sum=0;			// 执行 1 次基础操作
	for(i=0; i<n; i++)		// 执行 n + 1 次基础操作
	{
		sum = sum + i;		// 执行 n 次基础操作
	}
	printf("sum = %d\n",sum);// 执行 1 次基础操作
}

算法2：总共执行 3 次 基础操作

void algorithm2(int n)// 算法2：总共执行 3 次基础操作
{
	int sum=0;				// 执行 1 次基础操作
	sum = (1+n) * n/2;		// 执行 1 次基础操作
	printf("sum = %d\n",sum);// 执行 1 次基础操作
}

上面两个算法都是求解1加到n的结果的，当输入n=100时，请直观地判断这两个算法，哪个效率更高。很明显是 算法2 效率更高，运行时间较少，因为它只有 3 次基础操作，而 算法1 要执行2n+3=203次基础操作。

所以，估算 算法效率 的第一个步骤是找出该算法随着 问题输入规模n 的变化而变化的 基础操作次数，并用函数f(n)来表示这个关系。
例如：上面两个算法的 基础操作次数函数 可以分别表示为：
算法1：f(n) = 2n + 3
算法2：f(n) = 3

有了上面 基础操作次数 的认识之后，再来看 算法时间复杂度 就比较容易懂了，不然直接看概念可能会有点懵。

算法的时间复杂度：也就是算法的时间度量，记作T(n)=O(f(n))，表示随着 问题规模n 的增大，算法执行时间的增长率和f(n)的增长率相同。称作算法的渐近时间复杂度，简称时间复杂度。其中，f(n)是问题规模n的某个函数。
通常，用大写O( )来表示算法时间复杂度的记法。一般，随着问题规模n的增大，T(n)增长最慢的为最优算法。

从定义来看，时间复杂度是用大写O( )来表示的，括号里再写上一个函数f(n)，其实这个函数就是上面说的关于 基础操作次数 的函数使用大O阶法推导出来的。下面了解怎样推导大O阶。

推导大O阶的步骤：
1、用常数 1 取代运行次数函数中的所有加法常数；
2、在修改后的运行次数函数中，只保留最高阶项；
3、若最高阶项存在且不是 1 ，就去除与这个项相乘的常数。
经过这三个步骤，得到的就是大O阶。

🍟 用前面的两个算法的 基础操作次数 的函数为例推导大O阶：

f(n) = 3：用常数 1 取代所以加法尝试，得到f(n)=1，这已经是常数阶了，不需要后两步骤，再将f(n)=1替换到O(fn)中，得到大O阶O(1)

f(n)=2n+3：用常数 1 取代所以加法尝试，得到f(n)=2n+1，第二步，只保留最高阶项，得到f(n)=2n，最后去掉与这个项相乘的常数，得到f(n)=n，大O阶为O(n);

常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(logn) < (n) < O(nlogn) < O(n${}^2$) < O(n${}^3$) < O(2${}^n$) < O(n!) < O(n${}^n$)

给定一个算法的实现代码，估算 算法时间复杂度 时：
首先，要得出关于 问题规模n 的函数，也就是 基础操作执行次数函数f(n)；
其次，利用 大O阶推导法，推导出该算法的时间复杂度。用大写O( )表示。

void bubble_sort(int* Arr, int n)
{
	for (int i = 0; i < n; i++)				// 执行 n+1 次基础操作
	{
		for (int j = 0; j < n - i - 1; j++)	// 执行 n*(n-i-1) 次基础操作，也就是n^2-in-n次
		{
			//swap
			if (Arr[j] > Arr[j + 1])		// 执行 n*(n-i-1) 次基础操作，也就是n^2-in-n次
			{
				int temp = Arr[j];			// 执行 n*(n-i-1) 次基础操作，也就是n^2-in-n次
				Arr[j] = Arr[J + 1];		// 执行 n*(n-i-1) 次基础操作，也就是n^2-in-n次
				Arr[j + 1] = temp;			// 执行 n*(n-i-1) 次基础操作，也就是n^2-in-n次
			}
		}
	}
}

推导冒泡排序的时间复杂度的步骤：
①推导出基础操作执行次数函数：f(n)=(n+1) + 5n${}^2$ - 5in - 5n，这里的 i 可以当成常数处理；
②大O推导法第一个步骤，这里没有非 1 常数，跳过，得到f(n)=5n${}^2$ - 5in - 4n + 1；
③大O推导法第二个步骤，只保留最高阶项，f(n)=5n${}^2$；
④大O推导法第二个步骤，去除与这个项相乘的常数：f(n)=n${}^2$；
⑤用大O表示法表示时间复杂度为：O(n${}^2$)。

如果文章有帮助的话，点个赞让我知道一下 😁😁😁