以图明志

计算机算法

[专题] 快速排序里的学问:信息熵

从信息熵角度去理解问题
信息是个很抽象的概念。人们常常说信息很多,或者信息较少,但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到1948年,香农提出了“信息熵”的概念,才解决了对信息的量化度量问题。一条信息的信息量大小和它的不确定性有直接的关系。比如说,我们要搞清楚一件非常非常不确定的事,或是我们一无所知的事情,就需要了解大量的信息。

数据结构

[专题] 为什么要使用栈这种数据结构

缩小思考范围,聚焦问题核心
栈的引入简化了程序设计的问题,划分了不同关注层次,使得思考范围缩小,更加聚焦于我们要解决的问题核心。反之,像数组等,因为要分散精力去考虑数组的下标增减等细节问题,反而掩盖了问题的本质。所以现在的许多高级语言,比如Java、C#等都有对栈结构的封装,你可以不用关注它的实现细节,就可以直接使用Stack的push和pop方法,非常方便。

数据结构

[专题] 线性表顺序存储的优缺点

插入与删除的时间复杂度
先来看最好的情况,如果元素要插入到最后一个位置,或者删除最后一个元素, 此时时间复杂度为0(1),因为不需要移动元素的,就如同来了一个新人要正常排队,当然是排在最后,如果此时他又不想排了,那么他一个人离开就好了,不影响任何人。

数据结构

[专题] 第16话:算法的空间复杂度

时间与空间复杂度相互影响
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

数据结构

[专题] 第15话:算法的最坏情况与平均情况

复杂度就要看最坏情况
算法(Algorithms)的复杂度(Complexity)是指运行一个算法所需消耗的资源(时间或者空间)。同一个算法处理不同的输入数据所消耗的资源也可能不同,所以分析一个算法的复杂度时,主要有三种情况可以考虑,最差情况(Worst Case)下的,平均情况(Average Case)的, 最好情况(Best Case)下的。

数据结构

[专题] 第14话:如何计算算法的时间复杂度

大O记法的实践
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n}=0(f(n))。它表示随问题规模n的增大,算法执行时间的埔长率和 f(n)的埔长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f( n)是问题规横n的某个函数。

计算机算法

时间复杂度为O(1)的删除链表结点方法

从分析与思考中找到答案
这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解。在链表中删除一个结点,最常规的做法是从链表的头结点开始,顺序查找要删除的结点,找到之后再删除。由于需要顺序查找,时间复杂度自然就是O(n) 了。
1 / 1 首页 < Prev 1 Next > 尾页 页码: