菜单 学习猿地 - LMONKEY

danchun_xiaobai

数据结构与算法分析——开篇以及复杂度分析

danchun_xiaobai profile image danchun_xiaobai ・1 min read

开篇

你也许已经发现了,工作了几年,原以为已经是一只老鸟。但看到刚参加工作的同事,你发现,原来自己一直在原地踏步。跟新人相比,你的唯一优势就是对业务更熟悉而已,别的就没有什么优势了。

怎样才能够让自己更上一层楼呢?学习更多的框架?做更多项目?其实,程序员真正要做的是修炼内功,也就是夯实基础。比如设计模式、网络原理,当然也包括接下来要说的数据结构与算法分析。

一、为什么要学习数据结构与算法分析

  1. 告别烂代码,写出性能更好地代码。
  2. 解决问题的思路和方法,编程之外也有应用。
  3. 思考能力才是程序员的核心竞争力,而算法能够有效地锻炼这方面。

当然也有其他原因,进大厂、不被淘汰、完成领导对代码简洁度性能的要求。

二、如何学好

  1. 边学边练,一周用2~3个小时刷题。
  2. 带着疑问去学习,多想为什么。
  3. 学习算法是个需要沉淀的过程,切勿急于求成。

三、复杂度分析

复杂度分析是算法学习的精髓,几乎贯穿整个学习过程。掌握了复杂度分析,恭喜你,数据结构与算法分析的学习已经完成了一半。

  • 时间复杂度

大O时间复杂度实际并不是代码的真正执行时间,而是代码执行时间随数据规模增长而呈现的变化趋势。程序真正执行时间受环境以及数据规模影响很大,例如相同条件下i7处理速度肯定比i5快,i7处理器处理10条数据肯定比10W条块。
常见的空间复杂度就是 常量阶O(1)、线性阶O(n)、指数阶、对数阶O(logn)、线性对数阶O(nlogn),指数阶。

funtion sum (int n) {   
    int sum = 0;    
    for (int i=1; i <= n; i++) {    
        sum = sum + i;  
    }   
    return sum; 
}
# 第 2 行代码执行了一次,第 3 、4各执行了 n 遍。所以时间复杂度为 2n + 1 , 也就是 n 。
  1. 最好时间复杂度
  2. 最坏时间复杂度
  3. 均摊时间复杂度
    funtion find ( int[] array ,  int n ,  int m ) { 
    int position = -1;  
    for (; i < n; ++i) { 
        if (array[i] == m) {       
            position = i;       
            break;  
        }  
    }
    return position;
    }
    #如上代码,寻找m在数组中的位置。如果第一个元素就是 m 时间复杂度就是 1 。如果 m 不在数组中,时间复杂度就是 n 。这是就用到最好时间复杂度、最坏时间复杂度和平均时间复杂度。
    #最好情况,第一个元素就是m。所以,最好时间复杂度就是 1 。
    #最坏情况,m 不在数组中。所以,最好时间复杂度就是 n 。
    #均摊时间复杂度,此时共有 n + 1 可能性。每种情况累加后再除 n + 1,就是均摊时间复杂度。( 1 + 2 + 3 ..... n + n ) / ( n + 1 ) = n ( n + 3 ) / 2 ( n + 1 ) ,简化后就是 n 。
  • 空间复杂度

空间复杂度表示的是存储空间与数据规模之间的增长关系。

funtion getArray ( int n) {
    int i = 0;  
    int[] a = new int[n];
    for (  ; i <n; ++i) {  
        a[i] = i;  
    }
    return a;
}
#第 2 行代码申请了变量 a ,别处就没有再申请存储了。所以,空间复杂度就是 n 。

今日笔记主要内容是时间复杂度,只列举了简单的例子。

网上有很多题,建议大家去做下,熟能生巧是很有道理的。

以上内容,如有错误点或改进点,希望大家能够指出。有什么问题,也可以留言,大家一起讨论、学习,一起进步。

评论 (0)