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

求教

代码

计算

30 条回复 • 2014-06-02 02:18:13 +08:00

1

yangff

2014-05-29 16:38:05 +08:00

2

不存在。

2

misaka

2014-05-29 16:53:20 +08:00

1

目测算法。。。

3

zhoulujue

2014-05-29 17:24:23 +08:00

静态分析工具，多的是。

4

binux

2014-05-29 17:33:04 +08:00

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

5

imxz

2014-05-29 17:40:06 +08:00

是想问大O 吗？

6

Mutoo

2014-05-29 17:48:37 +08:00

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

7

karlxu

OP

2014-05-29 19:41:23 +08:00

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

8

karlxu

OP

2014-05-29 19:41:34 +08:00

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

9

karlxu

OP

2014-05-29 19:41:43 +08:00

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

10

jiang42

2014-05-29 20:13:09 +08:00

1

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

11

creamiced

2014-05-29 20:16:07 +08:00

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

12

akfish

2014-05-29 20:24:08 +08:00

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

13

akfish

2014-05-29 20:25:25 +08:00

1

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).

够严谨了吧。

14

keniusahdu

2014-05-29 20:27:45 +08:00

1

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

15

fzss

2014-05-29 21:19:59 +08:00

ORDER OF GROWTH

16

dorentus

2014-05-29 21:32:54 +08:00

1

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

17

soundbbg

2014-05-29 21:42:13 +08:00

1

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

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

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

18

ruandao

2014-05-29 23:21:14 +08:00

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

19

lijinma

2014-05-29 23:29:18 +08:00

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

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

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

20

soundbbg

2014-05-30 00:56:11 +08:00 via iPhone

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

21

66450146

2014-05-30 02:17:43 +08:00 via Android

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

22

karlxu

OP

2014-05-30 09:51:27 +08:00

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

23

karlxu

OP

2014-05-30 09:51:54 +08:00

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

24

akfish

2014-05-30 10:23:29 +08:00

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

25

karlxu

OP

2014-05-30 11:19:16 +08:00

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

26

akfish

2014-05-30 11:28:15 +08:00

1

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

27

wecing

2014-06-01 04:04:22 +08:00

我只知道停机问题。

28

lijinma

2014-06-01 23:32:50 +08:00

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

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

29

66450146

2014-06-02 00:36:01 +08:00 via Android

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

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

30

lijinma

2014-06-02 02:18:13 +08:00

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

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

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

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