Złożoność algorytmu w teście online

Question

Musiałem ukończyć test programowania online na staż i otrzymałem pytanie dotyczące analizy złożoności. Odpowiedziałem na pytanie i zostało oznaczone jako błędnie, i chciałbym tylko zrozumieć, dlaczego, więc mogę poprawić.

Pytanie:

Daj złożoność dla następującego algorytmu gdy reverseOrder jest prawdą, a kiedy jest fałszywe:

List<int> stackToList(Stack<int> stack, bool reverseOrder) { 
    List<int> items = new List<int>(); 

    while (stack.Count > 0) { 
     int item = stack.Pop(); 

     if (reverseOrder) { 
      items.Insert(0, item); 
     } else { 
      items.Add(item); 
     } 
    } 

    return items; 
} 

EDIT: Było multi-wybór , a możliwe odpowiedzi:

• O (1)
• O (nlogn)
• O (n)
• O (N^2)

Można wybrać jeden dla przypadku reverseOrder jest prawdziwa, a drugi, gdy to to fałsz.

My odpowiedzi:

• Po reverseOrder warunków: O (n)
• Gdy reverseOrder fałszywe: O (n)

I uzyskałem tę odpowiedź w następujący sposób:

• while Pętla będzie iteracyjne n razy, bo to trwa, dopóki nie istnieje żaden element w lewo, aby zasnąć
• Pop() jest O(1)

• W przypadku reverseOrder będąc true An Insert do przodu na liście jest zrobione. Od List<T> jest wspierany przez układ, jest zmieniany dynamicznie, i każdy element przemieszcza się o jedno miejsce, a element zostaje wstawiony na wskaźnik 0. Według https://msdn.microsoft.com/en-us/library/sey5k5z4(v=vs.110).aspx:

  Ta metoda jest O (n), działanie, gdzie n jest liczbą.

• W przypadku reverseOrder będąc false An Add jest wykonany, aby dołączyć pozycję do tyłu listy. Od items nie podano początkowego rozmiaru, Count nigdy nie jest mniejsze niż Capacity, powodując zmiany rozmiaru, tak według https://msdn.microsoft.com/en-us/library/3wcytfd1(v=vs.110).aspx:

  Jeśli liczba jest mniejsza niż moc ta metoda jest O (1) działanie.Jeśli pojemność musi zostać zwiększona, aby pomieścić nowy element, ta metoda staje się operacją O (n), gdzie n oznacza liczbę.

czuję się zupełnie zniechęca w tej chwili, ponieważ coraz to źle spowodował mój wynik gwałtownie spadły, choć mam wszystkie inne pytania na teście prawidłowe.

Answer 1

Musisz zapytać ludzi, którzy napisali test. Jakakolwiek tutaj odpowiedź byłaby oparta wyłącznie na opiniach, ponieważ nie mamy pełnego kontekstu, tj. Co skłoniłoby autora testu do opisania złożoności algorytmu w inny sposób niż ty.

To powiedziawszy, zgadzam się z autorem testu w scenariuszu reverseOrder == false. Chociaż jest prawdą, że użytkownik może wywołać operację zmiany rozmiaru podczas wywołania Add(), operacja zmiany rozmiaru wprowadziłaby w najgorszym przypadku koszt log N, ponieważ nowy rozmiar podwaja się wraz z każdą zmianą rozmiaru.

Nie mówisz, jaka powinna być poprawna odpowiedź, ale podałbym ją jako O (N log N).

Answer 2

Twoje założenie jest takie, że pojemność zwiększa się za każdym razem, gdy dodajesz element - to nie jest poprawne. W dokumentacji nie ma wzmianki o dokładnym algorytmie, ale uważam, że podwaja się za każdym razem, gdy zwiększa się pojemność. Widać, że w próbce o dinozaurach w dokumentacji związanej ty - dodają 5 dinozaury i raporty charakterze 8.

Answer 3

Patrząc na linii 6669 z

http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,cf7f4095e4de7646

Jest oczywiste, że przy wkładaniu początek listy wymusza kopiowanie do końca listy. Więc każda wstawka wymaga N ruchów. O (N^2) to mi się wydaje.

Answer 4

stackToList (stos, prawda) = O (n). W większości przypadków będzie to O (1). Jednakże, gdy funkcja List.Add musi rozwijać się bardziej niż jej pojemność, tablica musi zostać skopiowana do nowej tablicy o pojemności dwukrotnie większej niż poprzednia i powtórzona po poprzednich elementach, aby zapisać je w nowej tablicy. Jako takie, możemy reprezentować rzeczywistą operację w programie Excel jako IF (n LOG (n, 2) (n/2)/INT (n LOG (n, 2) (n/2)) = 1, n 1). Z uwagi na brak wąskich gardeł w zasobach, jeśli algorytm ten zakończy się w 10 sekund przy 10 milionach elementów, aby uzyskać 100 milionów elementów, można oczekiwać, że zajmie to około 10 (10) sekund. Realistycznie wiemy, że będzie on nieco gorszy niż Big O Notation przewiduje, ponieważ operacja O (n) będzie wymagała wielu operacji O (1).

powiększony, można zobaczyć, jak skumulowane operacje są dotknięte List.Copy()

pomniejszona, widać to naprawdę nie wpływa na wagę w porównaniu do O (n) operacji .

stackToList (stos, fałszywe) = O (N^2). Funkcja wstawiania listy wykonuje kopię tablicy, która musi przenieść wszystkie elementy na liście do nowej listy. Gdy wskaźnik rozpoczyna iterowanie przez stos macierzysty, liczba operacji rozpoczyna się od 0, a następnie rośnie, aż osiągnie n. Średnio występuje n/2 razy. Stała 2 jest usuwana w Big O Notation i pozostaje ci n.Z uwagi na brak wąskich gardeł w zasobach, jeśli algorytm ten kończył się w 10 sekund przy 10 milionach elementów, aby uzyskać 100 milionów elementów, można oczekiwać, że zajmie to około 10 (10^2) sekund. Realistycznie wiemy, że drugi przypadek będzie lepiej skalowany niż przewidywania Big O Notation, ponieważ w rzeczywistości jest to n * (n-1), ale nie będzie on miał skali większej niż O (n * Log (n)), następny krok na dół.

rozbić Operacji:

List<int> stackToList(Stack<int> stack, bool reverseOrder) { 
    List<int> items = new List<int>(); // O(1) 

    while (stack.Count > 0) {  // O(n): For every int in the supplied stack 
     int item = stack.Pop();  // O(1): https://referencesource.microsoft.com/#System/compmod/system/collections/generic/stack.cs,222 

     if (reverseOrder) {   // O(1) 
      items.Insert(0, item);  // O(n^2): https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,669 
     } else { 
      items.Add(item);   // O(Slightly more than 1): https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,220 
     } 
    } 
    return items; 
}