时间复杂度和空间复杂度

时间:2020-05-31 21:29:43   收藏:0   阅读:40

Big O notation

例题

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

类目 时间复杂度
二分查找 O(longn)
二叉树遍历 O(n)
排序类查找 O(n)
排序类 O(nlongn)

原文:https://www.cnblogs.com/ccaa/p/13021445.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!