• O(1):常数复杂度
• O(long n):对数复杂度
• O(n):线性时间复杂度
• O(n^2):平方
• O(n^3):立方
• O(2^n):指数
• O(n！):阶乘
  注意：在多个程序合在一起的时候，只看最高复杂度的运算

2|0例题

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