计算时间复杂度是评估算法执行时间随输入规模增长的增长率。通常通过分析算法中的循环、递归等操作来确定。可以使用大O符号表示,表示算法的最坏情况下的时间复杂度。计算时间复杂度时,需要考虑算法中每个操作的执行次数,并将其表示为输入规模的函数。然后,找到函数中的最高次项,忽略低次项和常数系数,得到时间复杂度。
确定基本操作 :从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作重复执行的次数作为算法的时间量度。计算操作次数:
分析算法中每个语句的执行次数,并将其表示为输入规模n的函数f(n)。
简化表达式
用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中,只保留最高阶项。
如果最高阶项存在且不是1,则去除与这个项相乘的常数。
表示时间复杂度:
将简化后的最高阶项用大O符号表示,即T(n)=O(f(n)),这称为算法的渐进时间复杂度。
示例
常数阶
```c
int sum = 0, n = 100;
sum = (1 + n) * n / 2;
```
时间复杂度为O(1),因为只有一个加法操作,与n无关。
线性阶
```c
for (int i = 1; i <= 100; i++) {
sum = sum + i;
}
```
时间复杂度为O(n),因为循环执行了100次,每次执行一次加法操作。
平方阶
```c
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= i - 1; j++) {
sum = sum + i;
}
}
```
时间复杂度为O(n^2),因为内层循环执行了(n-1)次,外层循环执行了100次,总的执行次数是100*(n-1)。
常见时间复杂度
O(1):
常数时间复杂度,如简单的加法、赋值等操作。
O(log n):对数时间复杂度,常见于分治算法中递归的深度。
O(n):线性时间复杂度,操作次数与输入规模n成正比。
O(n log n):常见于归并排序、快速排序等排序算法。
O(n^2):平方时间复杂度,常见于简单排序算法如冒泡排序、插入排序等。
O(n^3):立方时间复杂度,常见于某些递归算法。
O(2^n):指数时间复杂度,常见于递归算法中未优化的情况。
O(n!):阶乘时间复杂度,常见于某些递归算法,如旅行商问题。
通过以上步骤和示例,可以更好地理解和计算算法的时间复杂度。