程序 算法 时间复杂度

什么是程序设计?

答:程序设计是给出解决特定问题程序的过程，是软件构造活动中的重要组成部分。程序设计往往以某种程序设计语言为工具，给出这种语言下的程序。程序设计过程应当包括分析、设计、编码、测试、排错等不同阶段。

何为算法?它与程序有何区别?

答:算法是处理解决问题的思路及办法，程序语言是按照一定语法把算法表达来。

问题:什么是程序?计算理论中的问题?问题和程序之间的联系。

答:程序是可以编码成有限长字符串，同时能够使用一些存储保存必要的数据，并用约定的规则和方式对字符串进行操作。计算理论中的问题是具有某种性质的有限长字符串的集合。两者之间的关系是一个程序只能对应一个问题（字符串集合）。

问题:算法与计算的关系?

答:计算是一种将单一或复数之输入值转换为单一或复数之结果的一种思考过程。算法指的是一种计算过程或—问题的求解过程。两者的关系为:问题的求解是计算，求解算法中的每个步骤是计算；计算的过程是算法，算法又由计算步骤构成；计算的目的由算法实现，算法的执行由计算完成

陈春秀

问:程序与算法有哪些区别?

答:算法与程序:

（1）．一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。

（2）．程序中的指令必须是机器可执行的，而算法中的指令则无此限制。

（3）．算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序．

问:算法与程序两者之间有什么区别?

答:算法是由基本运算及规定的运算顺序所构成的完整的解题步骤，程序是计算机指令的有序集合，算法的范围比程序大，算法是解决问题的步骤，程序是算法的代码实现。

问题:算法与程序之间有什么联系?

答:算法就是程序的灵魂，一个需要实现特定功能的程序，实现它的算法可以有很多种，所以算法的优劣决定着程序的好坏。程序员很熟练的掌握了程序设计语言的语法，进行程序设计，软件开发的时候就是设计好的算法，加上软件工程的理论才能做出较好的系统。

问:算法的定义是什么?

答:   给定字母表，称以任何串为输入都能停机的图灵机为判定器。若一个语言有判定器，则称该语言可判定。判定器即为算法。

算法的任务是什么?

答:算法的任务是对输入串回答是与否。

算法有什么特点?

答:有穷性，确定性，输入，输出，可行性

算法具有哪些性质?

（1）通用性-适用于某类问题的求解

（2）能行性-有明确的求解步骤

（3）确定性-每个步骤都是机械的、明确的，无歧义

（4）有穷性-对某些输入在有限步内结束，并给出结果

（5）离散性-输入输出是离散的符号（数字和字母）

问题:算法的可行性是指什么?

答:简单的说就是:按着这个算法，是可以得出结果的，这种方法是可行的．

算法中所有操作都必须可以通过已经实现的基本操作及基本运算，并在有限次内实现，而且人们用笔和纸做有限次运算后也可以完成．

什么是不可处理的算法?什么是可处理的算法?

不可处理的算法往往所需要的时间复杂度是指数级别的，即便输入不大，也要消耗非常长的时间，一台普通计算机是难以算出来的。与之相反，可处理的算法的时间复杂度是多项式型的。

问:什么事程序?

程序是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。为实现预期目的而进行操作的一系列语句和指令。一般分为系统程序和应用程序两大类。

答:  1．一个有限长字符串      2．能够使用一些存储       3．约定了操作规则和方式

1．一个字符串

2．能够使用一些存储

3． 约定 了操作规则和方式

问题:计算机程序是什么?

答:计算机程序是指为了得到某种结果而可以由计算机等具有信息处理能力的装置执行的代码化指令序列，或者可以被自动转换成代码化指令序列的符号化指令序列或者符号化语句序列。

问题:计算机程序是什么?

答:计算机程序或者软件程序（通常简称程序）是指一组指示计算机每一步动作的指令，通常用某种程序设计语言编写，运行于某种目标体系结构上。

问: 从软件上讲什么是计算机程序?

答:所有的计算机应用程序其实都是通过一系列的算法来实现的。也就是说，为了解决实际问题，都将它转化为一个数学模型，然后通过计算机硬件的计算来解决实际问题。

问:计算机程序的执行过程?

答:在一台最常见的计算机上，程序从某种外部设备，通常是硬盘，被加载到计算机之内。 如果是我们现在使用的普通电脑结构，那么程序就被加载入内存。 指令串行顺序执行，直到一条跳转或转移指令被执行，或者一个中断出现。所有这些指令都会改变指令寄存器的内容。

问:计算理论中的判定器是什么?

答:在可计算性理论中，总是停机的机器也叫做判定器或全图灵机（对所有输入总是停机的图灵机）

问:请阐述计算复杂性的含义、度量标准及其含义。

答:计算复杂性就是用计算机求解问题的难易程度。其度量标准:一是计算所需的步数或指令条数（这叫时间复杂度），二是计算所需的存储单元数量（这叫空间复杂度）。 

时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。

空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。

什么是算法复杂度?

答:算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。

计算复杂性理论是计算理论的一部分，研究计算问题时所需的资源，比如时间和空间，以及如何尽可能的节省这些资源。

计算复杂性理论所研究的资源中最常见的是时间（要通过多少步才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。

问题:什么是算法的复杂度?

答:算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度）。

算法复杂度的意义? 

计算机系统中的任何软件，都是由大大小小的各种软件组成部分构成，各自按照特定的算法来实现，算法的好坏直接决定所实现软件性能的优劣．用什么方法来设计算法，所设计算法需要什么样的资源，需要多少运行时间，多少存储空间，如何判定一个算法的好坏，在实现一个软件时，都是必须予以解决的．计算机系统中的操作系统，语言编译系统，数据库管理系统以及各种各样的计算机应用系统中的软件，都必须用一个个具体的算法来实现．因此，算法设计与分析是计算机科学与技术的一个核心问题．

算法的时间复杂性是无穷大这个说法是否成立?

答:不成立，无穷大说明问题是不可解的，则不存在问题的计算复杂性。

算法的时间复杂度与空间复杂度的简单区别?

答:本质上，不论时间复杂度还是空间复杂度都反应的是问题本身的复杂度。一个计算要不就需要很大的存储空间来减少计算时间；要不就需要较长的计算时间来节约存储空间。

时间或空间复杂度也用来衡量各种计算方法对于不同的计算要求的表现。比如，不同的计算方法其实在时空复杂度上是相同的。

什么是空间复杂度?

类似于时间复杂度的讨论，一个算法的空间复杂度（SpaceComplexity）S（n）定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度（SpaceComplexity）是对一个算法在运行过程中临时占用存储空间大小的量度。

什么事时间复杂度?

答:计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

算法的时间复杂性是无穷大这个说法是否成立?

答:不成立，无穷大说明问题是不可解的，所以不存在计算无穷大

问:常见算法大致分为哪两大类?

答:一类是多项式时间内可实现的，另一类需要指数时间（O（cn））多项式时间算法的可实现性远大于指数时间算法。

问题:对于具有指数时间的问题，有些可用不确定性算法求解。该算法包括哪些阶段?

答:推测阶段:对规模为n的输入实例x，产生一个输出y

验证阶段:检验y是否满足解形式，是否是解

问题:常见的时间复杂度排序是?

答: O（1）＜O（㏒2n）＜O（n）＜ O（n㏒2n）: ＜O（n2）＜O（2n）

问题:一个算法的时间复杂度为指数时间，可以说明该问题是NP问题吗?

答:不可以，因为一个算法只是问题的一种方案，有可能存在另一种算法的时间复杂度为多项式时间，则该问题有可能为P问题。

问:请举一个多项式和非多项式的例子。

答:多项式:n＾3

非多项式:3＾n

问:什么是多项式时间算法?

答:如果П是任意一个问题，对П存

在着一个算法，它的时间复杂性为O（nk），其中n为输

入规模，k为非负整数，就认为存在着一个解问题П 

的多项式时间算法。

问:什么是多项式时间算法?

如果П是任意一个问题，对П存在着一个算法，它的时间复杂性为O（nk），其中n为输入规模，k为非负整数，就认为存在着一个解问题П 的多项式时间算法。

问题:什么是多项式时间?

答案:多项式时间在计算复杂度理论中，指的是一个问题的计算时间m（n）不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。

什么是伪多项式时间算法?

通俗得讲，算法的时间复杂度是输入数据的多项式表达，但却是输入数据长度的指数时间表达就是伪多项式时间算法

问:什么是多项式时间及其数学描述?

答:多项式时间指的是一个问题的计算时间m（n）不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。

m（n）＝ o（n＾k），此k为一常数值（依问题而定）。

问题:多项式时间考虑系数吗?

回答:不考虑

问:什么是多项式时间算法?

答:若存在一个常数C，使得对于所有n＞＝0，都有|f（n）| ＜＝ C*|g（n）|，则称函数f（n）是O（g（n））。时间复杂度是O（p（n））的算法称为多项式时间算法。

什么是伪多项式时间算法?

通俗得讲，算法的时间复杂度是输入数据的多项式表达，但却是输入数据长度的指数时间表达就是伪多项式时间算法

判断:不能用多项式时间求解的问题是NP问题。

回答:错误。因为P类问题属于NP问题中的一类，而P类问题能在多项式时间内求解。

问题:什么是多项式时间可解问题?

答:一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。

问题:问题的复杂性和算法的复杂性的区别是?

答:只就时间复杂性来说，算法的复杂性是指解决一个问题的算法执行的时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度。计算复杂性要研究的是后者。

问题:当n比较小时，多项式的值大于指数的值，是否可以说明多项式时间的算法用的时间比指数时间的算法用的时间多?

回答:不是的，当n大于某一个值后，指数的值会大于多项式的值，并且指数的值的增长速度远远大于多项式的值的增长速度。

问题:算法得时间复杂度是指它的最好情况、平均情况还是最坏情况?

答:最坏情况。因为只有最坏情况下的时间复杂度才能符合算法得所有情况。

问:为什么以多项式作为分界函数?

答:1、常见算法大致分为两类:一类是多项式时间内可实现的；另一类需要指数时间

2、多项式时间算法与计算模型无关

问题:问什么以多项式作为分界函数?

回答:因为常见算法大致分为两种——①多项式时间内可以实现的②需要指数时间（O（c＾n））；

多项式时间算法的可实现性远大于需要指数时间的算法；指数增长远大于多项式时间；而且多项式时间的复杂度忽略了系数，因此不影响易解问题与难解问题的划分；所以将指数时间算法归类为难解问题，在多项式时间内实现的算法归为易解问题；

所以把多项式时间复杂度作为易解问题与难解问题的分界线。

问:什么是时间复杂度?

答:在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

问:时间复杂度的求解方法?

答:1．找出执行次数最多的基本语句 

2． 计算执行次数的数量级 

3．用大O 表示算法的时间复杂度

问:计算复杂性是不是指时间复杂度?

回答:计算复杂性除了时间复杂度还包括空间复杂度

问:求解算法的时间复杂度的具体步骤是?

答:⑴ 找出算法中基本语句；　　

算法中基本语句是执行次数最多那条语句，例如最最内层循环的循环体。　　

⑵ 计算基本语句执行次数的数量级；　　

基本语句执行次数的数量级，是基本语句执行次数中的最高次幂，

可以忽略所有低次 幂和最高次幂的系数。　　

⑶ 用大Ο表示算法的时间复杂度。　　

将基本语句执行次数的数量级放入大Ο中。

问:什么是多项式时间?

答:在计算复杂度理论中，指的是一个问题的计算时间m（n）不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。

问:怎样的算法为之好的算法?

答:遵循Edmonds算法标准，即具有多项式时间的算法。