为有限元线性过程计数原理所做的图解

姜咏江

   大学问算法时间复杂度的提出已经多时了。然而与之相关的所谓P/NP问题却成了世界头号难题。问题出在哪里？是人类的逻辑思维论证不管用了？不！这一切都是概念上的含混不清造成的。问题出在计算机程序执行时间如何计算！用程序指令重复执行次数来计算的认识是人们公认的，然而如何计算呢？

   本人在《有限元线性过程计数原理》一文（连接附后）中作了探讨，给出了计算公式。本想在科学网上能有学者发声评判，可未如所愿。为通俗计，在此用图示方法给出计算公式的解释，望能觅友探讨。

   设程序执行的指令重复执行次数为M，那么有公式M=

，其中a_ij是第j层循环的i次循环的指令数。如果n_j用n表示，可以约定a_ij=0表示j层第i次循环模块不存在。

   为了形象地说明公式的计算方法，我们用图1给出了一个算法程序模块结构计算指令重复执行次数的示意图。图中椭圆第一个标注是循环嵌套层号，第二个标注是指令数，第三个标注是循环次数；实线连接的是循环嵌套模块内循环，虚线表示程序模块间执行的顺序过程。

图1  循环嵌套结构指令执行数计算过程

   图1中的0层是将不循环执行的部分都包含在其中了，循环从第1层开始。分支可以理解成子程序调用，如果是选择性分支，应该考虑执行过程中将不经历的部分去掉。

有限元线性过程计数原理：http://blog.sciencenet.cn/blog-340399-896333.html

2015-6-22