这个算法的复杂性是什么？我认为这是大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; 
    }