热门问题
时间线
聊天
视角

本质复杂度

来自维基百科,自由的百科全书

Remove ads

本质复杂度(Essential complexity)是指由于一问题的本质不适合简单的求解方式,所有可行的求解方式都很复杂的情形。本质复杂度和附属复杂度(Accidental 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(a[i] == 0) b[i] += 2;
  }

以下的C语言程式片段的本质复杂度为4,其控制流图无法再简化,其内容是要找到z阵列中第一个全部为0的列,若找到了,设定i为列编号,若找不到了,设定i为-1

      for(i=0;i<m;i++) {
          for(j=0;j<n;j++) {
              if(z[i][j] != 0) goto non_zero;
          }
          goto found;
  non_zero:
      }
      i = -1;
  found:
Remove ads

相关条目

参考资料

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads