渐进表达式

梗概

• 当n趋于无穷大时，表达式可以简化为导数差不多的渐进表达式

符号记法

O(变量)

求渐进表达式

简单方法

1. 如果F(n)为常数, 则为O(1)
2. 如果F(n)不为常数
   1. 取最高次数n
   2. 去掉系数和常数
3. k的n次方保留k

实例

1/n的渐进表达式

• 1/n 的渐进表达式可以用大O符号表示为 O(1/n)。
• 这意味着当 n 趋近于无穷大时，1/n 的增长速率不会超过某个常数 k，即存在一个正常数 k 和一个正整数 N，使得对于所有 n > N，1/n 都小于等于 k。
• 因此，1/n 的渐进复杂度是常数级别的，即它是一个非常快速的函数，增长速度比多项式级别的函数要慢很多。我们通常将这种渐进复杂度表示为 O(1)。
• 即当n无穷大时, 函数导数趋近于0, 所以简化为常数, 常数一般用1表示