- O(1):常数复杂度
- O(long n):对数复杂度
- O(n):线性时间复杂度
- O(n^2):平方
- O(n^3):立方
- O(2^n):指数
-
O(n！):阶乘
注意：在多个程序合在一起的时候，只看最高复杂度的运算
2|0例题
O(1)
int n=100; Console.WriteLine("Input:"+n);
O(N)
for(int i=1;i<=n;i++){ Console.WriteLine("Input:"+i); }
O(N^2)
for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ Console.WriteLine("Input:"+i+"and"+j); } }
O(long(n))
for(int i=1;i<=n;i=i*2){ Console.WriteLine("Input:"+i); }
O(K^n)
for(int i=1;i<=Math.Pow(2,n);i++){ Console.WriteLine("Input:"+i); }
O(N!)
for(int i=1;i<=Factorial(n);i++){ Console.WriteLine("Input:"+i); }
1+2+3+...+n
for i=1 to n:
y=i+y
这里需要计算n次
O(n)
求和公式：n(n+1)/2
y=n*(n+1)/2
无论n是多少，只计算一次
O(1)
递归:Fibonacci arry 1,1,2,3,5,8,13,21,34...
F(n)=F(n-1)+F(n-2)
def fib(n) if n==0or n==1 return n; return fib(n-1)+fib(n-2)
这里可以思考下他的时间复杂度
O(2^n)
这里记住背下master theorem