数据结构——算法底子

1、概念

算法(Algorithm)用来描述对特定问题的求解步骤，它是指令的有限序列，其中每一条指令代表一个或多个操作
算法的概念在计算机科学范畴中几乎无处不在，在各种计算机系统的实现中，算法的设计往往处于核心的位置。计算机的问世是20世纪算法是计算机科学的紧张底子，就像算盘一样，人们必要为计算机编制各种各样的“口诀”即算法，才华使其工作

软件(项目) = 程序 + 文档
程序 = 数据结构 + 算法
软件(项目) = 数据结构 + 算法 + 文档
2、特征

（1）有穷性：一个算法必须总是（对任何正当的输入值）实行有穷步以后结束，且每一步都可以在有穷的时间内完成
（2）确切性：算法中每一个指令都必须有确切的含义，读者和计算机在理解时不会产生二义性
（3）可行性：一个算法是能行的，即算法中描述的操作都是可以通过实行有效次基本运算来实现
（4）输入性：一个算法有零个输入或多个输入，以描画运算对象的初始环境
所谓0个输入，就是指算法自己给出了初始条件 int a=5;
3、描述

算法的描述形式多种多样，不同的描述形式对算法的质量有一定的影响。描述同一个算法可以采取自然语言、流程图(盒图)、伪代码以及程序设计语言等，常用的描述算法方法有如下四种:
（1）自然语言描述法
最简单的描述算法的方法是使用自然语言，用自然语言来描述算法的优点是简单且便于人们对算法的理解和阅读，缺点是不够严谨，易产生歧义。当算法比较复杂且包含很多转移分支时，用自然语言描述就不是那么直观清楚了
（2）算法框图法
使用程序流程图、盒图等算法描述工具来描述算法。其特点是简洁明了、便于理解和互换
（3）伪代码语言描述法
用上述两种方法描述的算法并不能够直接在计算机上实行。为了解决理解与实行之间的矛盾，人们常常使用一种称为伪代码语言的描述方法来对算法举行描述。伪代码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言或算法框图更接近程序设计语言
（4）高级程序设计语言描述法
使用特定的可以直接在计算机上实行的程序描述算法。优点是不消转换直接可以编译实行，缺点是必要对特定的程序设计语言比较理解。大部门的算法最终是必要通过能够向计算机发送一系列下令的程序来实现的
4、标准 

（1）正确性
算法至少应该具有输出、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案
（2）可读性
便于阅读、理解和互换
（3）结实性
当输入数据不正当时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果
（4）时间服从高与低存储量需求
时间服从指算法的实行时间，存储量主要指算法程序运行时所占用的内存或外部硬盘空间。设计算法应该尽量本着时间服从高和存储量低的要求
5、时间复杂度

对于一个算法的复杂性分析主要是对算法服从的分析，包括权衡其运行速度的时间服从，以及其运行时所必要占用的空间大小。对于算法的时间服从的计算，通常是抛开与计算机硬件、软件有关的因素，仅考虑实现该算法的高级语言程序。
算法的时间复杂度是一个函数，它定性描述该算法的运行时间，时间复杂度常用O表述，它权衡着一个程序的好坏，时间复杂度的估算是算法题的重中之重
（1）概念
要想计算时间复杂度起首得找到该算法中的循环，算法中循环实行的次数就是算法的时间复杂度
通常时间复杂度用一个问题规模函数来表达：T(n) = O(f(n))
①T(n)问题规模的时间函数
②n代表的是问题的规模输入数据量的大小
③O时间数目级
④f(n)算法中可实行语句重复实行的次数
（2）计算
函数的时间复杂度
        循环的次数，是一个常数               O(1)
        循环的次数，是一个n的一次幂      O(n)
        循环的次数，是一个n的两次幂      O(n^2)
例题：求下面函数的时间复杂度
   void func(){   
      int num = 0;
      for (int i = 0; i < N; i++) {   
        for (int j = 0; j < N; j++){   
            num++;   // 两层循环，每次循环n次，因此为n*n
        }
      }
      for (int k = 0; k < N; k++) {   
            ++num;   // 一层循环，   循环n次
      }
      for (int l = 0; l < 10; l++) {   
           ++num;   // 一层循环，循环10次
      }
}
  分析：
由解释，我们可以计算出时间的复杂度的表达式：N*N+N+10，但是我们能写成O(N*N+N+10)吗？
不能，我们知道对于时间复杂度，不必要算出正确的数字，只必要算出这个给算法属于什么量级即可，那么我们又如何知道它属于什么量级呢？
即：我们将字母取无穷大，例如本题中的字母为N，N取无穷大，而10对于N取无穷大后没有影响，因此10可以舍去，原表达式化为N*N+ N，再转化为N*(N+1)，由于N为无穷大，因此N+1，也是没有影响的，原式就变成了O(N*N)，也即O(N2)，这就是大无穷(O)渐进表现法，只是一种量级的估算，而不是正确的值

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。