中国航天建设集团有限公司网站,下载一个网站,软件商店下载安装2023版本最新,福建高速公路建设指挥部网站问题引出假设有一道题目#xff1a;有一组N个数而要确定其中第k个最大者#xff0c;我们称之为选择问题#xff0c;那么这个程序如何编写#xff1f;最直观地#xff0c;至少有两种思路#xff1a;1、将N个数读入一个数组中#xff0c;再通过某种简单的算法#xff0c;…问题引出假设有一道题目有一组N个数而要确定其中第k个最大者我们称之为选择问题那么这个程序如何编写最直观地至少有两种思路1、将N个数读入一个数组中再通过某种简单的算法比如冒泡排序法以递减顺序将数组排序则第k个位置上的元素就是我们需要的元素2、稍微好一些的做法将k个元素读入数组并以递减顺序排序接着将接下来的元素再逐个读入当新元素被读到时如果它小于数组中的第k个元素则忽略之否则将其放到数组中正确的位置上同时将数组中的一个元素挤出数组当算法终止时位于第k个位置上的元素作为答案返回这两种算法都很简单但是假设我们有一千万个元素的随机文件和k5000000进行模拟将发现两个算法尽管最终都可以给出正确答案但是在合理时间内均无法结束。因此这两种算法都不能被认为是好的算法因为从实际角度出发它们无法在合理的时间内处理输入的数据。数据结构和算法分析的提出在许多问题中一个很重要的观念是写出一个工作程序并不够。如果这个程序在巨大的数据集上运行那么运行时间就变成了重要的问题我们将在接下来的文章中看到对于大量的输入如何估计程序的运行时间尤其是如何在未具体编码的情况下比较两个程序运行的时间。我们还将看到彻底改进程序速度以及确定程序瓶颈的方法这些方法将使得我们能够发现需要我们集中精力努力优化的那些代码段。那么首先先了解一下什么是数据结构和算法分析(特别指出后文的例子均以Java代码编写)。数据结构数据结构是计算机存储、组织数据的方式是指数据相互之间存在一种或多种特定关系的数据元素的集合。通常情况下精心选择的数据结构可以带来更高的运行或者存储效率(这就是为什么我们要研究数据结构的原因)数据结构往往同高效的检索算法和索引技术相关。常见的数据结构有数组、栈、队列、链表、树、散列等这些数据结构将是本数据结构的分类中重点研究的对象。算法分析算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。对于一个问题一旦某种算法给定并且(以某种方式)被确定是正确的那么重要的异步就是确定该算法将需要多少注入时间或空间等资源量的问题。如果1、一个问题的求解算法竟然需要长达一年时间那么这种算法就很难有什么用处2、一个问题需要若干个GB的内存的算法在当前大多数机器上也是无法使用的数学基础无论是数据结构还是算法分析都用到了大量的数学基础下面将这些数学的基础简单总结一下1、指数(1)XAXB XAB(2)XA/XB XA-B(3)(XA)B XABsi(4)XN XN 2XN ≠ X2N(5)2N 2N 2N 12、对数(1)XA B当且仅当logxB A(2)logAB logCB / logCA(3)logAB logA logBA0且B03、级数(1)∑2i 2N1 - 1(2)∑Ai (AN1 - 1) / (A - 1)若0i ≤ 1 / (1 - A)4、模运算如果N整除A、N整除B那么就说A与B模N同余记为A≡B(mod N)。直观地看这意味着无论是A还是B被N去除所得余数都是相同的于是假如有A≡B(mod N)则(1)A C ≡ B C(mod N)(2)AD ≡ BD (mod N)时间复杂度在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数时间复杂度常用大O符号表述不包括这个函数的低阶项和首项系数使用这种方式时时间复杂度可被称为是渐进的他考察当输入值大小趋近无穷时的情况。那么首先先看一个简单的例子这里是计算Σi3的一个简单程序片段 1 public static void main(String[] args) 2 { 3 System.out.println(sum(5)); 4 } 5 6 public static int sum(int n) 7 { 8 int partialSum; 9 10 partialSum 0;11 for (int i 0; i n; i)12 partialSum i * i * i;13 14 return partialSum;15 }对这个程序片段的分析是简单的1、声明不记入时间2、第10行和都14行各占一个时间单元3、第12行每次执行占用4个时间单元(两次乘法、一次加法和一次赋值)而执行N次共占用4N个时间单元4、第11行在初始化i测试i≤n和对i的自增都隐含着开销所有这些总开销是初始化1个时间单元所有的测试为N1个时间单元所有自增为N个时间单元共2N2个时间单元忽略调用方法和返回值的开销得到总量是6N4个时间单元按照最开始的定义不包括这个函数的低阶项和首项系数因此我们说该方法的时间复杂度是O(N)。继而我们顺便得出若干个一般法则法则一----for循环一个for循环的运行时间至多是该for循环内部那些语句(包括测试)的运行时间乘以迭代的次数因此假如一个for循环迭代N次那么其时间复杂度应该为O(N)法则二----嵌套for循环从里向外分析这些循环在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积因此假如有以下代码 1 public static int mutliSum(int n) 2 { 3 int k 0; 4 for (int i 0; i n; i) 5 { 6 for (int j 0; j n; j) 7 { 8 k; 9 }10 }11 12 return k;13 }则其时间复杂度应为O(N2)法则三----顺序语句将各个语句的运行时间求和即可比如有以下代码 1 public static int sum(int n) 2 { 3 int k 0; 4 5 for (int i 0; i n; i) 6 k; 7 for (int i 0; i n; i) 8 { 9 for (int j 0; j n; j)10 {11 k;12 }13 }14 15 return k;16 }第一个for循环的时间复杂度为N第二个嵌套for循环的时间复杂度为N2综合起来看sum方法的时间复杂度为O(N2)常见的时间复杂度与时间效率的关系有如下的经验规则O(1) O(log2N) O(N) O(N * log2N) O(N2) O(N3) O(N!)至于每种时间复杂度对应哪种数据结构和算法后面都会讲到从上面的经验规则来看前四个算法效率比较高中间两个差强人意最后一个比较差(只要n比较大这个算法就动不了了)。
