计算机科学

首页 > 计算机科学

本质复杂度

2018-08-23 10:11:58     所属分类:程式设计小作品

本质复杂度(Essential complexity)是指由于一问题的本质不适合简单的求解方式,所有可行的求解方式都很复杂的情形。本质复杂度和偶然复杂度不同,后者的复杂度和问题本质无关,和选用求解的工具或方法有关。

本质复杂度至少在1980年代中期已被使用,图灵奖得主佛瑞德·布鲁克斯当时已开始使用本质复杂度及其反义词偶然复杂度。他也在1995年时在《人月神话》中的没有银弹一段中提出他的新论点[1][2][3] [4]

循环复杂度

若本质复杂度和循环复杂度并用时,本质复杂度有不同的含意。此时的本质复杂度是指一程式持续的将有良好结构的流桯控制指令改为单一叙述后,最后得到的循环复杂度。像if-then-else及while loop等控制结构都视为良好结构,因此不会增加本质复杂度。未限制使用的goto、break及continue指令会增加本质复杂度。

例如,以下的C语言程式片段的本质复杂度为1,因为内层的if指令及for循环都可以简化为单一叙述。

  for(i=0;i<3;i++) {
     if(ai == 0) bi += 2;
  }

以下的C语言程式片段的本质复杂度大于1,其内容是要找到z阵列中第一个全部为0的列,若找到了,设定i为列编号,若找不到了,设定i为-1

      for(i=0;i<m;i++) {
          for(j=0;j<n;j++) {
              if(zij != 0) goto non_zero;
          }
          goto found;
  non_zero:
      }
      i = -1;
  found:

相关条目

  • 决策到决策路径
  • 偶然复杂度
  • 奥卡姆剃刀
  • 没有银弹

参考资料

  1. ^ Brooks, Fred P. No Silver Bullet - Essence and Accident in Software Engineering. Proceedings of the IFIP Tenth World Computing Conference. 1986: 1069–1076. 
  2. ^ Brooks, IEEE Computer
  3. ^ Brooks, Mythical Man-Month, Silver Bullet Refired
  4. ^ McCabe, Watson. Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric Chapter 10: Essential Complexity. 1996. (原始内容存档于2012-08-28). 

上一篇:Shell脚本
相关推荐