Jakie są złożoność czasu i przestrzeni tego algorytmu?

Obliczam złożoność czasu WC, która ma być następująco:

  1. wszystkie inicjacje do (1) każdy

  2. za pętlę, aby być o (n), ponieważ

    • zewnętrzny do pętli, aby uruchomić max z N razy,
    • Inicjaty, które mają być kosztami 1 każdego,
    • wewnętrzny dla pętli, aby uruchomić maks. 17 razy, a
    • The instrukcje i zadania, które mają być kosztami 1 każdego.
    • Obliczam O ((n + 1 + 1) * (17 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), a następnie ignorowanie stałej O (N) .
  3. Złożoność czasu drugiej części algorytmu, która ma być następująca:

    • inicjacja listy do kosztów 1
    • do pętli do 17
    • Rozpoczęcie spotkania do kosztów 1
    • if instrukcja ma koszt 1
    • inicjacja indexofendtime, aby być 1
    • do pętli do 16
    • jeśli stwierdzenie było 1
    • przypisanie do 1 każdego
    • O (1+ (17 + 1 + 1 + 1 + 1 + 1 + 1) * (16 + 1 + 1 + 1 + 1) +1), która jest po prostu stała Powiedz c.
  4. T (n) = etap 1 + etap 2 + etap 3 = O (1 + N + C), co oznacza, że moja najgorsza złożoność czasu na czas jest O (N).

Czy to jest poprawne? Czy możesz potwierdzić, czy moje obliczenia było poprawne? W tym przypadku najlepsza złożoność czasu na czas będzie O (1)? Czy ma sens, aby rozważyć przeciętny przypadek i jeśli to robi, jak to zrozumieć?

Wreszcie obliczam najlepszą / średnią / najgorszą złożoność przestrzeni, która ma być 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;
    }
3
PAujla 17 styczeń 2020, 01:05

1 odpowiedź

Najlepsza odpowiedź

Twoja najgorsza analiza wydaje się być całkowicie poprawna; Nie zauważyłem w nim żadnych błędów i otrzymuję ten sam wynik.

Twoja najlepsza analiza jest nieprawidłowa; Powiedziałeś, że potrzeba o (1) czasu w najlepszym przypadku, ale pętla na liście meetings zawsze kończy iteracje n , więc tak również ma również o ( n ) czas. Być może popełniłeś błąd, zakładając, że długość listy wynosi 1 lub nawet 0 w najlepszym przypadku; To nie liczy się jako "przypadek", ponieważ musisz rozważyć rodzinę wejść parametryzowanych przez rozmiar n do analizy asymptotycznej, aby mieć w ogóle sens.

Twoja analiza złożoności przestrzeni nie jest również poprawna. Twój algorytm tworzy dwie struktury danych: tablica slots ma stały rozmiar, a lista {X1}} ma również mieć stałą wielkość, ponieważ dołączony jest tylko z trzeciej pętli, którą założyliśmy O (1) Operacje, więc liczba operacji add do tej listy jest również O (1). Nawet jeśli ta lista zakończyła się o rozmiarze O ( n ), jest to wyjście do algorytmu, więc każdy algorytm musiałby utworzyć listę tego rozmiaru ; Zwykle jest to bardziej przydatne do pomiaru "pomocniczej" złożoności przestrzeni, tj. przestrzeń używaną przez tymczasowe struktury danych, które istnieją tylko dla działań wewnętrznych algorytmu.

Istnieje jeden założenie, które byłoby przydatne do stacji jawnie, co jest, że spotkanie startTime i endTime i {X1}} jest zawsze ograniczone w zakresie od 0 do 16 (włącznie), dzięki czemu ma sens do użycia jako Indeks w slots. Nawiasem mówiąc, nie musisz wymyślać nazwy dla stałej {x3}}, możesz po prostu pisać O (1) tam.

3
kaya3 16 styczeń 2020, 22:50