计算机公式的复杂度通常通过大O表示法来计算,它描述了算法运行时间或所需空间与输入规模之间的关系。以下是计算复杂度的一些关键步骤和技巧:
时间复杂度
定义:时间复杂度表示算法运行所需时间与输入规模之间的关系,通常用大O表示法表示,即T(n)=O(f(n)),其中T(n)表示算法运行的时间复杂度,f(n)表示输入规模n的函数。
常见的时间复杂度分类:
O(1):算法的运行时间与输入规模无关。
O(logn):算法的运行时间与输入规模的对数成正比。
O(n):算法的运行时间与输入规模成正比。
O(nlogn):算法的运行时间与输入规模的对数乘以线性成正比。
O(n^2):算法的运行时间与输入规模的平方成正比。
O(n^3):算法的运行时间与输入规模的立方成正比。
O(2^n):算法的运行时间与输入规模的指数成正比。
O(n!):算法的运行时间与输入规模的阶乘成正比。
空间复杂度
定义:空间复杂度表示算法在处理规模为n的问题时所需的额外空间。
表示方法:与时间复杂度类似,空间复杂度也通常用大O表示法表示,即S(n)=O(f(n))。
复杂度计算技巧
最高次项法则:在多项式式子中,保留最高项,忽略其他项和常数。
加法法则:将算法整体运行时间分为若干个部分,在加和计算中,忽略低阶项和常数。
示例
计算一个简单循环的时间复杂度
```python
def calc(n):
sum_ = 0
for i in range(1, n+1):
sum_ = sum_ + i
return sum_
```
执行时间T(n) = 1 + 2 + ... + n = n(n+1)/2,所以时间复杂度为O(n^2)。
计算一个嵌套循环的时间复杂度
```python
def calc(n):
sum_ = 0
for i in range(n):
for j in range(n):
sum_ = sum_ + i * j
return sum_
```
执行时间T(n) = n * n * n = n^3,所以时间复杂度为O(n^3)。
结论
通过以上步骤和技巧,可以有效地计算计算机公式的复杂度。理解不同时间复杂度分类及其对应的算法特征,有助于选择合适的算法来解决特定问题。