本文最后更新于 2022年01月09日 已经是 508天前了 ，文章可能具有时效性，若有错误或已失效，请在下方留言。
n := 100
x := 0
for i := 1; i <= n; i++ {
for j := 1; j <= i; j++ {
for k := 1; k <= j; k++ {
x++
}
}
}
log.Println(x)
分析循环次数
| i | j | k | 内层循环次数 |
|---|---|---|---|
| 1 | [1] | [1] | 1 |
| 2 | [1,2] | [1][1,2] | 3 |
| 3 | [1,2,3] | [1][1,2][1,2,3] | 6 |
| … | |||
| n | [1,2,3,…,n] | [1][1,2][1,2,3]…[1,2,3,…,n] | 1+2+3+…+n |
计算循环次数
循环次数
$n=\sum_{x=1}^{n}\frac{\left ( 1+x\right )x}{2}$
$\sum_{x=1}^{n}\frac{\left ( 1+x\right )x}{2}=\frac{1}{2}\left (\sum_{x=1}^{n}x+\sum_{x=1}^{n}x^{2}\right )$
其中
$\sum_{x=1}^{n}x^{2}=\frac{x\left ( x+1\right )\left ( 2x+1\right )}{6}$
最后
$\sum_{x=1}^{n}\frac{\left ( 1+x\right )x}{2}=\frac{1}{2}\left (\frac{x(x+1)}{2}+\frac{x\left ( x+1\right )\left ( 2x+1\right )}{6}\right )=\frac{x\left ( x+1\right )\left ( x+2\right )}{6}$
带入n=100,计算得x=171700
程序运行结果
C:\Users\enjoy\AppData\Local\Temp\GoLand\___go_build_dataStructure.exe
2022/01/09 11:54:10 171700
结果一致
此处3层循环的时间复杂度为O(n^3)
