亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

尋找大 O 復雜度。三種算法

尋找大 O 復雜度。三種算法

守候你守候我 2022-06-23 10:28:10
我試圖找到以下算法的時間復雜度。從我可以看到 alg1 中的前兩個循環是n^2但是我不確定 alg2 中的循環的運行時間是多少。public class algo {public static int alg1(int[] A, int n) {    int l = 0;    for (int i = 0; i <= n-1; i++) {        for (int j = i+1; j <= n-1 ; j++) {           if(alg2(A,i,j) && j-i > l) {               l = j-i+1;           }        }    }    return l;}private static boolean alg2(int[] A,int i, int j) {    if(i==j) {        return true;    }    for (int k = i; k <= j-1; k++) {        if(A[k] != A[k+1]) {            return false;        }    }    return true;}}
查看完整描述

2 回答

?
浮云間

TA貢獻1829條經驗 獲得超4個贊

您是正確的,第一個 Alg1 的時間復雜度為 O(n^2)。第二個函數 Alg2 的時間復雜度為 O(n),因為算法的性能將與其輸入大小成正比線性增長。您只有一個 for 循環,并且您沒有在該代碼的任何地方應用 D&C 技術。



查看完整回答
反對 回復 2022-06-23
?
溫溫醬

TA貢獻1752條經驗 獲得超4個贊

alg2是 O(n)

alg1因為它alg2在內部 for 循環內所以它應該是 O(n^2 * n) = O(n^3)。如果你想證明:

http://img1.sycdn.imooc.com//62b3cfe60001ad7b03850630.jpg

查看完整回答
反對 回復 2022-06-23
  • 2 回答
  • 0 關注
  • 101 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號