算法-复杂度分析


复杂度分析

Big O notation

注意:只看最高复杂度的运算

  • O(1):Constant Comlexity 常数复杂度
  • O(log n):Logarithmic Complexity 对数复杂度
  • O(n):Linear Complexity 线性时间复杂度
  • O(n^2):N square Complexity 平方
  • O(n^3):N square Complexity 立方
  • O(2^n):Exponential Growth 指数
  • O(n!):Factotial 阶乘

O(1)

int n =1000;
System.out.println("Hey - your input is:" + n);

O(?)

int n =1000;
System.out.println("Hey - your input is:" + n);
System.out.println("Hmm.. I'm doing more stuff with::" + n);
System.out.println("And more:" + n);

O(n)

for(int i =1; i<=n; i++){
    System.out.println("Hey - I'm busy looking at:" + i);
}

O(N^2)

for(int i =1;i<=n;i++){
    for(int j = 1; i<=n; j++){
        System.out.println("Hey - I'm busy looking at:" + i +" and" + j);
    }
}

O(log(n))

for(int i = 1; i < n; i=i*2){
    System.out.println("Hey - I'm busy looking at:" + i);
}

O(k^n)

int fib(int n){
    if(n<=2) return n;
    return fib(n-1) + fib(n-2);
}

时间复杂度、空间复杂度

时间复杂度曲线

image-20200711201752044

循环

计算:1 + 2 +3 + …. + n

方法一:从1到n的循环累加

y = 0;
for i = 1 to n:
    y += i

方法二:求和公式 sum = n(n+1)/2

y = n * (n + 1)/2

递归

Fib:0,1,1,2,3,5,8,13,21,……..

  • F(n)=F(n-1)+F(n-2)
  • 面试(直接用递归)
int fib(int n){
    if (n<=2) return n;
    return fib(n-1) + fib(n-2);
}
image-20200711203432792

Master Theorem

image-20200711203626143

思考题

  1. 二叉树遍历-前序、中序、后序:时间复杂度是多少

    • O(n)
  2. 图的遍历:时间复杂度是多少?

    • O(n)
  3. 搜索算法:DFS、BFS时间复杂度是多少?

    • O(n)
  4. 二分查找:时间复杂度是多少?

    • O(log n)

文章作者: 韩思远
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 韩思远 !
评论
 上一篇
技术基础 技术基础
技术基础 洞悉技术的本质,享受科技的乐趣 https://coolshell.cn/ 程序员如何用技术变现 程序员用自己的技术变现,其实是一件天经地义的事儿。写程序是一门“手艺活儿”,那么作为手艺人,程序员当然可以做到靠自己的手艺和技能养
2020-08-31
下一篇 
算法前言 算法前言
前言 如何高效的学习数据结构和算法? 期待效果 职业顶尖级别——对算法的理解 一线互联网公司面试 LeetCode 300+的积累 精通一个领域 Chunk it up 切碎知识点 庖丁解牛 脉络连接 Deliberate Prac
2020-08-31
  目录