简答题

结合克拉默给出的用于分析程序复杂性的几个例子,分析结构与复杂性的关系。

正确答案

当系统的结构不能被描述,或描述它的最小算法与系统本身具有相同的信息比特数时,则称该系统为根本复杂系统。在达到根本复杂之前,人们仍可以编写出能够执行的程序,否则,做不到。
例如,序列“aaaaaaa…”是一个亚(准)复杂性系统;相应的程序为:在每一个a后续写a。这个短程序使得这个序列得以随意复制,不管要多长都可以办到。
序列“aabaabaabaab…”与上一个例子相比要复杂一些,但仍可以很容易地写出程序:在两个a后续写b并重复这一操作。
序列“aabaababbaabaababb…”也可以用很短的程序来描述:在两个a后续写b并重复,同时,每当第三次重写b时,将第二个a替换为b。这样的序列具有可定义的结构,有对应的程序来表示。
最后考察序列“aababbababbbabaaababbab…”,该序列没有结构,若想编程,则必须将字符串全部列出。

答案解析

相似试题
  • 切换同时打开的几个程序窗口的操作方法有()。

    多选题查看答案

  • 面向对象的程序设计它的几个特征是什么?

    简答题查看答案

  • 在浏览器中应当有几个可选解释程序。试给出一些可选解释程序的名称。

    简答题查看答案

  • 分析下列程序段,给出执行结果:

    简答题查看答案

  • 分析下列程序段执行情况,给出结果:

    简答题查看答案

  • 下面是一段求最大值的程序,其中datalist是数据表,n是datalist的长度。 (1)画出该程序的控制流图,并计算其McCabe环路复杂性。 (2)用基本路径覆盖法给出测试路径。 (3)为各测试路径设计测试用例。

    简答题查看答案

  • 请用分治策略设计递归的归并排序算法,并分析其时间复杂性(要求:分别给出divide、conquer、combine这三个阶段所花的时间,并在此基础上列出递归方程,最后用套用公式法求出其解的渐进阶)。

    简答题查看答案

  • 下面的函数用于比较两个给出的C字符串。按比较结果,函数将返回下列函数值:请补充程序()()()

    填空题查看答案

  • 请给出宏定义的几种定义形式。

    简答题查看答案