이 알고리즘의 복잡성은 무엇입니까? I는 큰 O (N)라고 생각 -

Question

IOS는 정렬되지 않은 배열의 상위 4의 정수를 위해 해결해야https://github.com/HarrisonJackson/iOS-find-top-4-integers-in-big-list---also-use-blocks-and-delegates

알고리즘 프로젝트 ... 루프에만 1을 사용. 여기서는 정렬되지 않은 NSNumber의 목록을 생성하고 반복합니다 - 상위 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; 
    }