复杂度和执行时间

平时我们在刷题的时候可以根据参数的大小来估算需要的复杂度。

但是这个估计是个相当粗糙的估计。因为语言的不同。假如用java或者golang来刷题，那么每句你写的line，都要被转化成机器语言。而这个转换率肯定和语言有关，也和调用内部程序有关。

今天我用的机器的CPU的频率(GHz)：2.7。即每秒能够处理2_700_000_000机器指令。

今天用的语言是golang，那么虽然我只写了几十行代码lines，可我也估算不出来转化成机器指令会有多少行。

目前只能实测然后推导了。推导出的数字似乎也没有什么通用性，因为下次的指令可能不同。

在网上找到这个猜每秒执行多少iteration的

https://computers-are-fast.github.io/

1. go tool compile -S main.go

复制代码

可以把30行的golang代码反汇编成大概400多行机器语言。

其中最关键的几个loop之一代码是19行

1. "".merge STEXT size=405 args=0x48 locals=0x30
   
2.         0x0096 00150 (main.go:19)        MOVQ        (R9), R11
   
3.         0x0099 00153 (main.go:19)        MOVQ        (DX), R12
   
4.         0x009c 00156 (main.go:19)        CMPQ        R11, R12
   
5.         0x009f 00159 (main.go:19)        JGE        199
   
6.         0x00a1 00161 (main.go:20)        CMPQ        R10, CX
   
7.         0x00a4 00164 (main.go:20)        JCC        388
   
8.         0x00aa 00170 (main.go:20)        MOVQ        R11, (AX)(R10*8)
   
9.         0x00ae 00174 (main.go:21)        DECQ        R8
   
10.         0x00b1 00177 (main.go:21)        MOVQ        R8, R11
    
11.         0x00b4 00180 (main.go:21)        NEGQ        R8
    
12.         0x00b7 00183 (main.go:21)        SARQ        $63, R8
    
13.         0x00bb 00187 (main.go:21)        ANDQ        $8, R8
    
14.         0x00bf 00191 (main.go:21)        PCDATA        $2, $4
    
15.         0x00bf 00191 (main.go:21)        ADDQ        R9, R8
    
16.         0x00c2 00194 (main.go:21)        DECQ        DI
    
17.         0x00c5 00197 (main.go:21)        JMP        123
    
18.         0x0184 00388 (main.go:20)        CALL        runtime.panicindex(SB)
    
19.         0x0189 00393 (main.go:20)        UNDEF
    
20.         0x018b 00395 (main.go:20)        NOP
    

复制代码

大概和1.73Sec的运行时间对上。当然这个对上可能是voodoo。

另外可以

1. go test -bench=. -cpuprofile=/tmp/cprof
   
2. go tool pprof -png /tmp/cprof

复制代码

来生成出一个break down。