算法与数据结构是一个老生常谈的问题了,这是一个基本的码农素养。但是我发现很多人并不理解,甚至不懂却还不在乎这些看似基本的东西。所以这里,我将用一些篇幅,介绍一些常见数据结构与算法,为了让更多的人容易理解,本系列文章会使用多种语言进行实践,如C/C++、OC、Swift、Python、JavaScript、Java、Go等。

1再识算法

1.1算法概念

算法算法,到底何为算法呢?简单的来说,算法就是一系列明确的指令来告诉计算机确切的执行步骤来处理一个指定的问题或任务。通俗的来说,就是你告诉计算机要怎么去干这件事情的。算法是计算机处理信息的本质,当计算机处理信息是,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。

算法是一种思想,一种解决问题的方法

对于一种算法,实现语言并不重要,算法可以有不同语言的实现版本,重要的是思想。

1.2算法特性

算法具有五大特性

  1. 输入:算法具有0个或多个输入。
  2. 输出:算法至少有1个或多个输出。
  3. 有穷性:算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在可接受的时间内完成。
  4. 确定性:算法中的每一步都有确定的含义,不会出现二义性[1]
  5. 可行性:算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完成。

1.3算法效率

1.3.1 执行时间

要如何衡量一个算法的效率优劣好坏呢,很容易想到的就是比较算法的执行时间,同一个问题,多个算法,运行时间的快慢很容易就分出了高下。
但是,单靠运行时间值可靠吗?任何一种程序算法的运行都离不开计算机环境,不同硬件配置的计算机性能有这极大的差距,系统软件环境也影响着程序的执行。这些客观的环境和不同程度的影响对算法时间的测试,所以这并不可靠。(当然,在很多情况下,我们可以简单粗略的用运行时间来进行一些算法性能的测试)

1.3.2时间复杂度大O表示法

假设计算机执行算法时,每个基本操作的时间是一个固定的时间单位,那一个执行了多少个基本操作就会花费多少个时间单位。对于不同的计算机环境而言,时间单位是不同的,但是对于算法来说,执行了多少个基本操作在规模数量级上是相同的,也就是说,花费了多少时间单位在规模数量级上是相同的。通过时间单位花费的比较,就可以忽略计算机环境而影响而客观反应算法的时间效率。

对于算法的时间效率,用大O表示法来进行表示。

大O表示法:称一个函数g(n)是O(f(n)),当且仅当存在常数c>0和n0>=1,对一切n>n0均有|g(n)|<=c|f(n)|成立,也称函数g(n)以f(n)为界或者称g(n)受限于f(n)。记作g(n)=O(f(n))。 定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时,时间复杂度的极限情形称为算法的“渐近时间复杂度”。[2]
对于大O表示法,学过高数中数列极限的同学们应该很容易理解,具体会在后边实践中介绍。

1.3.3最坏时间复杂度与时间复杂度基本计算规则

分析算法时,可能会进行以下考虑:

  • 算法完成工作最少需要多少基本操作,即最优时间复杂度
  • 算法完成工作最多需要多少基本操作,即最坏时间复杂度
  • 算法完成工作平均需要多少基本操作,即平均时间复杂度

最优时间复杂度是最理想的一种情况,例如对某个数组排序,可是没有排序之前这个数组中数据的排列顺序就是我们需要的顺序。所以并最优时间复杂度没有什么参考价值。

平均算法复杂度可以全面性的反应这个算法的性质,但是这个衡量并没有保证的,不是每次计算都能在这个复杂度范围内完成,就像有一个大奖,中奖概率50%,但是真的到了你身上,不是0%就是100%。

最坏时间复杂度可以说是提供了一种保证,在最坏时间复杂度程度中,我们的计算任务是一定可以完成的,这是最坏的情况,但也是保障,是我们最需要关注的。

时间复杂度具有以下一些准规则

  1. 基本操作,即只有常数项,认为其时间复杂度为O(1)
  2. 顺序结构,时间复杂度按加法进行计算。
  3. 循环结构,时间复杂度按乘法进行计算。
  4. 分支结构,时间复杂度取分支中最大值
  5. 判断一个算法的效率时,通常只需要关注操作数量的最高次项,其它次要项和常数项可以忽略。
  6. 在没有特殊说明时,所分析的算法的时间复杂度通常都是指最坏时间复杂度

2数据结构

2.1概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。[3]

通常在计算机中,为了解决问题,需要将数据进行存储,然后根据数据的存储方式来设计算法进行处理,数据存储的不同方式就会导致需要不同的算法进行处理。不同算法的效率不同,我们希望算法解决问题的效率越快越好,于是就需要考虑我们的数据到底如何存储的问题了。

数据是一个抽象的概念,在不同程序设计语言中有着不同的表现,如一些数字,字符等。数据直接存在某种特定关系,相互并不独立,这些关系就组成了结构。数据结构就是描述数据元素直接的关系。

2.2 算法与数据结构

数据结构静态的描述了数据元素直接的关系,我们的程序任务处理需要在数据结构的基础上选择和设计算法。可以认为:

程序 = 数据结构 + 算法

算法是为了解决实际问题,数据结构便是算法需要处理的问题的载体。


先给大家介绍了一些比较枯燥的概念性东西,在后续文章将展开具体实践

微信 OR 支付宝 扫描二维码
给复仇者码农 打个赏吧  
微信打赏   支付宝打赏  
金额随意 快来“打”我呀~

发表评论