求教：计算代码复杂度的算法是什么？

[yangff]

不存在。

[misaka]

目测算法。。。

[zhoulujue]

静态分析工具，多的是。

[binux]

http://zh.wikipedia.org/wiki/%E5%81%9C%E6%9C%BA%E9%97%AE%E9%A2%98

[imxz]

是想问 大O 吗 ？

[Mutoo]

大O表示法，在 Mark Allen Weiss 的《数据结构与算法分析》里面有专门一章节介绍，而且有好几章节的案例分析。

[karlxu]

@imxz 我想问的是圈复杂度计算，网上都是说数有多少if，while，for。。。。但感觉不是很严谨

[karlxu]

@Mutoo 我想问的是圈复杂度计算，网上都是说数有多少if，while，for。。。。但感觉不是很严谨

[karlxu]

@binux 我想问的是圈复杂度计算，网上都是说数有多少if，while，for。。。。但感觉不是很严谨

[jiang42]

@karlxu 难道你想分析到机器码级别的？
算法分析个大概就好
然后放到实际环境中跑跑看看

[creamiced]

@karlxu 圈复杂度当然是数这些啊，当然还要考虑嵌套。
还以为你说时间复杂度

[akfish]

http://en.wikipedia.org/wiki/Cyclomatic_complexity

[akfish]

Mathematically, the cyclomatic complexity of a structured program[a] is defined with reference to the control flow graph of the program, a directed graph containing the basic blocks of the program, with an edge between two basic blocks if control may pass from the first to the second. The complexity M is then defined as[2]
M = E − N + 2P,
where
E = the number of edges of the graph.
N = the number of nodes of the graph.
P = the number of connected components (exit nodes).

够严谨了吧。

[keniusahdu]

Sonar 有计算复杂度的。但是没有什么算法，都是针对循环，判断之类的识别。以及空引用高危判断。
ps:我说的是java ，其他不知道

[fzss]

ORDER OF GROWTH

[dorentus]

https://zh.wikipedia.org/wiki/循環複雜度
这个？
按定义数呗
本来就不是啥严禁的

[soundbbg]

一开始不需要过度优化，后面针对具体的瓶颈优化就好了。

拿循环做复杂度其实也挺逗的，谁知道函数嵌套了多少个函数，更不要说大部分不间断的程序都是死循环，你没看到只是因为别人都封装好了。

代码里不推荐多个嵌套循环这是必然的，但纯拿循环来说性能就和拿代码行数算KPI一个道理，况且计算机就是一个大循环。

[ruandao]

时间复杂度?
空间复杂度?
还是逻辑复杂度?

[lijinma]

@soundbbg 拿循环说性能挺逗？大哥，那你觉得纯研究算法的是靠什么来做标准？还不是靠循环，你这是藐视算法分析；

一个算法在数据很小的时候没多大作用，但是在数据很大的时候，n^2 和 n 那得有多大差距啊；

敢问兄弟，不靠循环，你靠什么来评判一个算法的时间复杂度？

[soundbbg]

@lijinma 你理解错了，我没有藐视算法。

[66450146]

@lijinma 算法的时间复杂度跟代码本身没有任何关系，也不是由循环数量决定的。。。简单的可以数循环，复杂的就数不出来了

[karlxu]

@akfish 我们要用python做个统计代码复杂度的工具，难道就数if,while,for,try,catch,switch?会不会太简单了？

[karlxu]

@soundbbg 我们要用python做个统计代码复杂度的工具，难道就数if,while,for,try,catch,switch?会不会太简单了？

[akfish]

@karlxu 正经的方法是把编译器前端部分做出来，解析源代码生成AST（抽象语法树），剩下的事情就是一堆图算法去撸而已。
这部分的研究很成熟了，各种IDE高上洋的代码自动完成、重构、分析工具都是这样实现的。

[karlxu]

@akfish 好像挺难的。。。多谢你的建议。

[akfish]

@karlxu Parser有现成的可用，不用自己写
https://docs.python.org/2/library/ast.html

[wecing]

我只知道停机问题。

[lijinma]

@66450146 无语，我倒要问问你了，你写代码的时候，还写过估算不出时间复杂度的代码？

如果你真估算不出来，我还是建议你不要写这样的代码为好。

[66450146]

@lijinma 我不会先写代码再从代码来计算时间复杂度，我相信你也是的。。。比如说最优化问题，复杂度就要从这个问题的信息量和筛选(剪枝)的效率或者是DP的规模来推断，从这个角度上来说代码的循环数量和复杂度都是同一个原因的结果，而不能说代码是复杂度的原因，就算代码一行都没写，复杂度也丝毫不会受到影响，不知道这样说清楚不清楚。。。

如果只是简单的深搜广搜或者裸 DP，那当然是数数就好了。。。

[lijinma]

@66450146 恩，看来我们的观点是不矛盾的；

（1）我们自己写代码，肯定是先由算法，有时间复杂度，然后才有代码；

（2）但我们去看别人的代码，我们可以参考（我说的是参考，不一定完全依赖）别人代码中的循环等来估算别人的代码复杂度；

-。- 所以，我们说的是两个问题，不过你同意（2）的内容吗？