這個算法的複雜性是什麼？我認爲這是大O（N） - for ... in循環

Question

IOS項目https://github.com/HarrisonJackson/iOS-find-top-4-integers-in-big-list---also-use-blocks-and-delegates

的算法應該解決在排序的數組前4個整數只使用1。在這裏，我生成一個未排序的NSNumbers列表，並對它進行迭代 - 保持排名前4的列表。我將解決方案提交給代碼挑戰，但被告知解決方案實際上不是O（n）。

// Generate the array self.numbers and unset the top 4 self.topN 
// ... 
// Use built in fast-enumeration to iterate over array of NSNumbers 
    for (NSNumber * num in self.numbers) { 
     // Make sure that all 4 of the top4 numbers is initialized 
     if(!self.top1){ 
      self.top1 = num; 
      continue; 
     } 
     if(!self.top2){ 
      self.top2 = num; 
      continue; 
     } 
     if(!self.top3){ 
      self.top3 = num; 
      continue; 
     } 
     if(!self.top4){ 
      self.top4 = num; 
      continue; 
     } 

     // Adjust our top4 as we fly over the array 
     if([self.top1 intValue] < [num intValue]){ 
      self.top1 = num; 
      continue; 
     } 
     if([self.top2 intValue] < [num intValue]){ 
      self.top2 = num; 
      continue; 

     } 
     if([self.top3 intValue] < [num intValue]){ 
      self.top3 = num; 
      continue; 

     } 
     if([self.top4 intValue] < [num intValue]){ 
      self.top4 = num; 
      continue; 

     } 

    } 

更新感謝的快速反應 - 這個問題似乎不能與算法，但邏輯的複雜性。當發現更大的價值時，我沒有將數字推到前4名 - 哎呀！哈哈。這裏有一個針對任何有類似問題的人的更新算法。我也會發布我的完整項目解決方案。

for (NSNumber * num in self.numbers) { 
     // Make sure that all 4 of the top4 numbers are initialized 
     if(!self.top1){ 
      self.top1 = num;     
      continue; 
     } 
     if(!self.top2){ 
      self.top4 = self.top3; 
      self.top3 = self.top2; 
      self.top2 = num; 
      continue; 
     } 
     if(!self.top3){ 
      self.top3 = num; 
      continue; 
     } 
     if(!self.top4){ 
      self.top4 = num; 
      continue; 
     } 

     // Adjust our top4 as we fly over the array 
     if([self.top1 intValue] < [num intValue]){ 
      self.top4 = self.top3; 
      self.top3 = self.top2; 
      self.top2 = self.top1; 
      self.top1 = num; 
      continue; 
     } 
     if([self.top2 intValue] < [num intValue]){ 
      self.top4 = self.top3; 
      self.top3 = self.top2; 
      self.top2 = num; 
      continue; 

     } 
     if([self.top3 intValue] < [num intValue]){ 
      self.top4 = self.top3; 
      self.top3 = num; 
      continue; 

     } 
     if([self.top4 intValue] < [num intValue]){ 
      self.top4 = num; 
      continue; 

     } 

    } 

Answer 1

邏輯錯誤，但算法是O（n）。對於每一步，只有持續的操作量。

邏輯錯誤是，當您替換某個點的數字時，您需要向下推送先前的值，例如，

if([self.top1 intValue] < [num intValue]){ 
     self.top4 = self.top3; 
     self.top3 = self.top2; 
     self.top2 = self.top1; 
     self.top1 = num; 
     continue; 
    }