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

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

使用兩個指針的算法的時間復雜度是 0(n) 還是 0(n^2)

使用兩個指針的算法的時間復雜度是 0(n) 還是 0(n^2)

狐的傳說 2022-12-18 16:16:49
所以這是給出的問題。給定一個整數數組,返回一個新數組,其中新數組中的每個元素都是原始輸入數組中該元素右側較小元素的數量。例如,給定數組 [3, 4, 9, 6, 1],返回 [1, 1, 2, 1, 0],因為:There is 1 smaller element to the right of 3There is 1 smaller element to the right of 4There are 2 smaller elements to the right of 9There is 1 smaller element to the right of 6There are no smaller elements to the right of 1我想出了這個雙指針算法。 function lessThan(arr) {  let results = [];  let i = 0;  let j = arr.length - 1;  let count = 0;  while (i < arr.length) {    if (arr[i] > arr[j]) {      count++;    }    j--;    if (j === 1) {      results.push(count);      count = 0;      i++;      j = arr.length - 1;    }  }  return results;}指針“i”將從開頭開始,“j”將從結尾開始。如果'j'等于1.'i'遞增并且'j'重置為末尾。這一直持續到'i'到達數組的末尾。(當'i'等于或大于arr.length while循環中斷)。根據我對時間復雜度的了解。我猜我們只遍歷數組一次是 O(n)。但是我們不應該考慮這樣一個事實,即在我們進行的過程中對“j”進行了“n”次比較嗎?我是競爭性編程和大 O 符號的新手。請幫助我。
查看完整描述

2 回答

?
PIPIONE

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

它是O(n2)i ,你每次迭代都會遞增len(arr),直到ireach len(arr)。

len(arr) * len(arr) 這在即O(n2)中給出了復雜性。


查看完整回答
反對 回復 2022-12-18
?
UYOU

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

您可以將代碼重新排列為


 function lessThan(arr) {

  let results = [];

  let i = 0;

  while (i < arr.length) {

    let j = arr.length - 1;

    let count = 0;

    while (j !== 1) {

      if (arr[i] > arr[j]) {

        count++;

      }

      j--;

    }

    results.push(count);

    i++;

  }

  return results;

}

是的,您巧妙地將嵌套循環合并為一個循環,但這并沒有改變它的復雜性。請注意,在您的版本中,while循環運行arr.length 2次數i不是在每次迭代時遞增,而是僅在j == 1.


從我的更新版本中,不僅可以清楚地看到代碼是O(n2),而且它是錯誤的:j !== 1(or j > 1) 應該比較i而不是1- 你只想計算右邊的元素。


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

添加回答

舉報

0/150
提交
取消
微信客服

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

幫助反饋 APP下載

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

公眾號

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