首頁猿問如何找到這個嵌套for循環(huán)的復(fù)雜性？

如何找到這個嵌套for循環(huán)的復(fù)雜性？

Java

慕碼人2483693 2022-09-22 19:24:34

我對這個循環(huán)有點困惑。給定一個數(shù)字n，我們必須找出指令執(zhí)行多少次。forint j = 0;for(int p = 0; p < n*n; p++ ){ for(int q = 0; q < p; q++ ) { j++; }}我的回答是.這個答案正確嗎？O(n^4)

查看完整描述

1 回答

人到中年有點甜

TA貢獻(xiàn)1895條經(jīng)驗獲得超7個贊

您可以為時間復(fù)雜度編寫相關(guān)的西格瑪。因此，您的答案對于說明的數(shù)量是正確的。T(n) = sum_{p = 1}{n^2} sum_{q=1}{p} (1) = sum_{p=1}{n^2} (p) = 1 + 2 + 3 + ... + n^2 = n^2(n^2 + 1)/2 = Theta(n^4)

反對回復(fù) 2022-09-22