В чем сложность этого алгоритма? Я думал, что это был большой O(N) - используя только 1 для... в цикле

Question

Проект ios https://github.com/HarrisonJackson/iOS-find-top-4-integers-in-big-list---also-use-blocks-and-delegates

Алгоритм должен найти 4 верхних целых в несортированном массиве. Здесь я генерирую список несортированных номеров NSN и перебираю его, поддерживая список 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;
    }