三层循环时间复杂度
    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)

高性能,高性价比服务器推荐! 可能需要科学的方法
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇