Какова временная и пространственная сложность этого алгоритма? - PullRequest
Новая
       6

Какова временная и пространственная сложность этого алгоритма?

3 голосов
/ 17 января 2020

Какова временная и пространственная сложность этого алгоритма?

Я вычисляю сложность времени W C следующим образом:

  1. все инициации должны быть O (1) каждый

  2. для l oop, чтобы быть O (n), потому что

    • внешний для l oop, чтобы работать максимум из n раз ,
    • инициации будут стоить 1 каждый,
    • внутренний для l oop, чтобы работать максимум 17 раз, и
    • операторы if и назначения должны быть стоимостью 1 каждый.
    • Я вычисляю O ((n + 1 + 1) * (17 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), затем игнорирую постоянную O (n).

  3. временная сложность второй части алгоритма следующая:

    • Начало списка будет стоить 1
    • для l oop равным 17
    • Инициирование собрания должно стоить 1
    • , если утверждение будет стоить 1
    • Инициирование indexOfEndTime будет 1
    • для l oop, чтобы быть 16
    • , если оператор будет 1
    • , присвоение будет 1 каждый
    • O (1+ ( 17 + 1 + 1 + 1 + 1 + 1 + 1) * (16 + 1 + 1 + 1 + 1) +1), который является просто постоянным значением, скажем c.

  4. T (n) = Шаг 1 + Шаг 2 + Шаг 3 = O (1 + n + c), что означает, что моя сложность времени в худшем случае - O (n).

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

Наконец, я рассчитываю, что наилучшая / средняя / наихудшая сложность пространства равна O (n). 

    public static List<Meeting> mergeRanges(List<Meeting> meetings) {
        byte available = 0;
        byte reservedBlockStart = 1;
        byte reservedBlockMiddle = 2;
        byte reservedBlockEnd = 3;
        byte[] slots = new byte[17];

        for(Meeting meeting : meetings) {
            byte startTime = (byte) meeting.getStartTime();
            byte endTime = (byte) meeting.getEndTime();
            for(byte i = startTime; i <= endTime; i++) {
                if(slots[i] == available) {
                    if(i == startTime) {
                        slots[i] = reservedBlockStart;
                    } else if(i == endTime) {
                        slots[i] = reservedBlockEnd;
                    } else {
                        slots[i] = reservedBlockMiddle;
                    }
                } else if(slots[i] == reservedBlockStart) {
                    if(i != startTime) {
                        slots[i] = reservedBlockMiddle;
                    }
                } else if(slots[i] == reservedBlockEnd) {
                    if(i != endTime) {
                        slots[i] = reservedBlockMiddle;
                    }
                }
            }
        }

        List<Meeting> condRange = new ArrayList<Meeting>();
        for(byte i = 0; i < slots.length; i++) {
            Meeting meet = new Meeting(0,0);
            if(slots[i] == reservedBlockStart) {
                byte indexOfEndTime = i;
                meet.setStartTime(i);
                for(byte j = (byte)(i + 1); j < slots.length; j++) {
                    if(slots[j] == reservedBlockEnd) {
                        meet.setEndTime(j);
                        indexOfEndTime = j;
                        j = (byte)(slots.length - 2);
                    } 
                }
                condRange.add(meet);
                i = (byte)(indexOfEndTime - 1);
            }
        }
        return condRange;
    }

1 Ответ

3 голосов
/ 17 января 2020

Ваш анализ наихудшего случая кажется полностью правильным; Я не заметил никаких ошибок в этом, и я получаю тот же результат.

Ваш анализ в лучшем случае неверен; вы сказали, что в лучшем случае это O (1), но ваш l oop по списку meetings всегда завершает n итераций, поэтому этот случай также принимает O ( n ) время Возможно, вы допустили ошибку, предполагая, что длина списка в лучшем случае равна 1 или даже 0; это не считается «случаем», потому что вам нужно рассмотреть семейство входов, параметризованных размером n , чтобы асимптотический c анализ имел смысл вообще.

Ваше пространство Анализ сложности также не является правильным. Ваш алгоритм создает две структуры данных: массив slots имеет постоянный размер, а список condRange также имеет постоянный размер, потому что он добавляется только к третьему l oop, который, как мы установили, делает O (1) операций, поэтому число операций add в этом списке также равно O (1). Даже если этот список в конечном итоге будет иметь размер O ( n ), он является выходом алгоритма, поэтому любой правильный алгоритм должен будет создать список такого размера; обычно полезнее измерять сложность «вспомогательного» пространства, то есть пространства, используемого временными структурами данных, которые существуют только для внутренней работы алгоритма.

Существует одно предположение, которое было бы полезно явно указать, а именно: что собрания startTime и endTime всегда ограничены диапазоном от 0 до 16 (включительно), так что имеет смысл использовать в качестве индекса в slots. Кстати, вам не нужно придумывать имя для константы c, вы можете просто написать O (1) там.

...