数据结构与算法 - 时间复杂度

目录

一、数据结构概要 二、算法概要 三、时间复杂度简介 四、求解时间复杂度

一、数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在各类实际应用问题中，数据元素之间总是存在着各种关系，描述数据元素之间关系的方法称为结构。通常，可根据数据元素之间所存在的关系的不同特征，用4类基本结构予以描述： (1)集合：指结构中的数据元素之间只存在“同属一个集合”的关系。 间 (2)线性结构：指结构中的数据元素之间存在“一个对一个”的关系。 数 (3)树形结构：指结构中的数据元素之间存在“一个对多个”的关系。 (4)图形结构：指结构中的数据兀素之间存在“多个对多个”的关系。

基本结构

二、算法

2.1、算法定义：

通常，算法( Algorithm)是指解决问题的一种方法或一个过程。如果把问题看作函数，则算法就能把输入转化成输出。 在数据结构中，算法是对特定问题求解步骤的一种描述，是指令的有限序列。 同一问题可以有多种不同的求解算法，一个给定的算法可以用来描述解决特定问题的一个具体的求解方案。了解对于同一问题的多种求解法有助于对算法的运行效率进行分析和比较，加深对算法的理解。

2.2、算法设计：

算法设计技术是用算法解题的一般性方法，用于解决不同计算领域的多种问题。 常用的算法设计技术主要有蛮力法、分治法、减治法、变治法、时空权衡、动态规划、贪婪技术等。 1、蛮力法 蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。可以应用蛮力法解决广阔领域的各种问题，它是唯一一种几乎什么问题都能解决的一般性方法。 2、分治法 分治法将问题的实例划分为若干个较小的实例，对这些较小实例递归求解，然后合并这些解，以得到原始问题的解。 3、减治法 减治法通过建立一个问题给定实例的解和同样问题较小实例解的关系，采用自顶向下(递归)或自底向上(非递归)的策略进行求解。 减治法有三个主要的变种：减一技术(每次迭代减去一个常量，通常为1)、减半技术(每次选代减去一个常量因子，通常为2)、减可变规模技术(每次选代规模减小的模式不同)。 4、变治法 变治法基于变换的思想，将问题变换成更容易求解的形式。 变治法有三个策略：实例化简(把问题的实例变换为相同问题的另一个实例，使问题的求解更加容易)、改变表现(将一个问题实例的表现改变为同样实例的另一种表现)、问题化简(把一个给定的问题变换成另一个可以用已知算法求解的问题) 5、时空权衡 时空权衡主要有空间换时间和时间换空间两种技术。在早期的计算机应用中，硬件资源限制严重，许多问题包含的大量数据无法整体装入计算机中一次处理，需要通过时间换空间技术才能解决；但在硬件资源十分丰富的现在，算法设计通常采用空间换时间技术。 空间换时间技术有两类，输入增强技术，通过对问题输入的部分或全部做预处理，以来提高算法的时间效率。 加速问题的求解；预构造技术，通过使用额外的空间来实现更快或更方便的数据存取。 6、动态规划 动态规划是一种对具有交叠子问题的问题进行求解的技术。一般来说，这样的子问题出现在求解给定问题的递推关系中，而该递推关系包含了相同类型更小问题的解。它通过对每个较小的子问题求解一次并记录在表中，从而避免对交叠子问题的重复求解，从表中得出原始问题的解。 7、贪婪技术 贪婪技术通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。贪婪技术核心是，所做的每一步选择都必须满足可行、局部最优和不可取消原则。

2.3、算法分析

估量一个算法或计算机程序效率的方法，称为算法分析。所谓算法分析，就是对一个算法所消耗的资源的估算。算法分析的目的主要是考察算法的时间效率和空间需求，分别从算法的时间复杂度和空间复杂度两个方面进行分析，如果存在多个可行的算法，则根据时间复杂度或空间复杂度这两个指标选取效率最高最优的算法。

进行算法分析需要了解的基本概念： (1)问题规模：一般是指输入量的数目。 (2)基本操作：通常是指具有完成该操作所需的时间与操作数的取值无关的性质的 操作。 (3)代价：即实现一个算法所需的资源需求。 (4)增长率：是指当问题规模增大时，算法代价增长的速率。 (5)最佳、最差和平均代价：分别是指算法实现对资源需求的最小、最大和平均情况。

三、时间复杂度

算法的时间复杂度是指算法对时间的需求。一个算法的运行时间通常与所解决问题的规模大小有关。 例如，在排序问题中，排序的元素个数n就是问题规模，排序算法中基本操作语句的重复执行次数随着问题规模n的增大而增加。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)。因此，算法的时间效率可记为：T(n)= O(f(n)) 表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。表达式中O的含义是指T(n)的数量级。一般情况下，当Tn)为多项式时，可只取最高次幂项，且系数也可省略。例如：T(n)=3n²+n-9 则T(n)=O(n²)。 一般地，算法所消耗的时间是每条语句的执行时间之和。每条语句的执行时间是其执行次数(频度)与该语句执行一次所需时间的乘积。在计算机中，程序语句的执行时间与计算机的性能有关，因此在分析算法的执行效率时，假设语句执行时间与机器无关，只考虑所有语句的执行次数。 算法中的基本操作可以理解为算法程序中最深层循环内的语句中的基本操作，它的执行次数(频度)与包含它的语句的执行次数相同。 通常情况下，时间复杂度的表示以O(f(n))形式体现，如O(1)、O(n)、O(n²)、O(logn)、O(2^n )等。根据f(n)的具体形式，常称某个算法的时间复杂度是常量阶O(1)线性阶O(n)、平方阶O(n²)、对数O(logn)、指数阶O(2^n)等。常数阶表示算法的时间复杂度与问题规模n无关。当一个算法的时间复杂度体现为指数阶时，通常将认为不是一个有效的算法。

空间复杂度是指算法执行过程对计算机存储空间的要求，称为算法的空间复杂度。类似于时间复杂度，记为 S(n)= O(f(n)) 其中n是问题的规模 通常，执行一个算法程序除了需要存储空间存放本身所用的指令、常数、变量和输出数据外，还需要一些辅助空间用于对数据进行处理及存储处理过程中的中间信息。若输入数据所占的空间只取决于问题本身而与算法无关，则只需要分析除了输入和程序之外的辅助空间需求。算法的空间复杂度通常就是指这种辅助空间需求的大小。

四、求解时间复杂度

最后通过实例来加深对时间复杂度的理解：

• 【例1】以下算法实现奇偶性判断，试分析时间复杂度。

int isOdd (int n) {
  if(n % 2 == 0) {   //(1)
    return 1:         //(2)
   }else {
    return 0;  //(3)
  }
}

分析：语句(1)执行1次，根据表达式n%2==0结果，可能执行语句(2)或语句(3)1次。
语句总执行次数为T(n)=1+1=2
因此，算法的时间复杂度为常数阶O(1)。算法的执行时间与问题规模n无关。

• 【例2】递归算法实现求n！，试分析时间复杂度。

int fact(int n) {
 if(n <= 1) {
    return 1;  //(1)
   }else {
    return(n * fact(n-1));  //(2)
   }
}

分析：语句(1)的时间复杂度为O(1)，递归调用fact(n-1)的时间是T(n-1)，因此可得
当n≤1时，T(n) = O(1)，
当n>1时:T(n) = T(n-1) + O(1)，T(n-1)=0(1)+T(n-2)，T(n-2)=O(1)+T(n-3）........
由此可推出
T(n)=(n-1)0(1)+T(1)=O(n)
因此递归求n！算法的时间复杂度为O(n)。