Zrozumienie notacji Big O - pękanie wywiadu kodowania

Question

Potrzebuję pomocy w zrozumieniu, w jaki sposób autor otrzymał odpowiedź na problem 11 w rozdziale "Wielka O.".

Problem wygląda tak:

następujące wydruki Kodeksu wszystkie ciągi o długości k, gdzie znaki są w posortowanych. Czyni to, generując wszystkie ciągi o długości k, a następnie sprawdzając, czy każdy jest posortowany. Jakie jest jego środowisko uruchomieniowe?

public static int numChars = 26; 

public static void printSortedStrings(int remaining) { 
    printSortedStrings(remaining, ""); 
} 

public static void printSortedStrings(int remaining, String prefix) { 
    if (remaining == 0) { 
     if (isInOrder(prefix)) { 
      System.out.println(prefix); // Printing the string 
     } 
    } else { 
     for (int i = 0; i < numChars; i++) { 
      char c = ithLetter(i); 
      printSortedStrings(remaining - 1, prefix + c); 
     } 
    } 
} 

public static boolean isInOrder(String s) { 
    for (int i = 1; i < s.length(); i++) { 
     int prev = ithLetter(s.charAt(i - 1)); 
     int curr = ithLetter(s.charAt(i)); 
     if (prev > curr) { 
      return false; 
     } 
    } 
    return true; 
} 

public static char ithLetter(int i) { 
    return (char) (((int) 'a') + i); 
} 

public static void main(String[] args) { 
    printSortedStrings(2); 
} 

Book odpowiedź:

O (kc ^k), gdzie k jest długością łańcucha, a C jest liczba znaków w alfabecie. Trwa O (c ^k) czas, aby wygenerować każdy ciąg. Następnie musimy sprawdzić, czy każdy z nich jest posortowany, co zabiera czas O (k).

Zauważ, że drukowanie sznurka nie jest brane pod uwagę w powyższej odpowiedzi, ale widziałem przeciwne w innych problemach.

Kiedy bierzesz pod uwagę drukowanie napisu w środowisku wykonawczym?

będzie to poprawna odpowiedź O (k c ^k)?

Sugerowana jest także jakakolwiek rada dotycząca szybkiego stwierdzenia, że ​​w środowisku wykonawczym tego kodu występuje wykładnicza część. :)

Answer 1

W skrócie, nie. Prawidłowa odpowiedź to O (kc ^k), podobnie jak w książce.

Po przejściu przez ciąg znaków w celu sprawdzenia, czy jego znaki zostały zamówione, co zajmie O (k), wydrukowanie doda tylko O ​​(k) - co nie zmieni złożoności.

Załóżmy, że sprawdzenie, czy łańcuch jest zamówiony, wykonuje operacje a*k, a drukowanie zajmuje b*k. Łączna liczba operacji dla każdego ciągu wynosi co najwyżej (a+b)*k, który wciąż jest O (k).

Edit: W odniesieniu do drugiej części pytania, przechodząc przez wszystkie słowa z jakimś stałej długości spowoduje wykładniczej złożoności wykonawczego, ponieważ istnieje c ^k takich słów gdzie c jest wielkość alfabetu i k jest długością słowa.

Answer 2

Drukowanie ciągu jest tylko dodatkowym dodatkiem do czasu k.

Sprawdzenie czy każdy łańcuch jest posortowana jest O(k) i powiedzieć, że drukowanie jest O(dk) jakiegoś całkowitej d (stałą). Dodając dwa otrzymujemy O(k + dk), który można ponownie napisać jako O(k(1 + d)). Ponieważ to tylko skalar, znamy O(k + dk) = O(k), więc odpowiedź się nie zmienia.

Answer 3

Ogólnie rzecz biorąc, drukowanie ciągów o stałej długości jest uważane za stałe, ale jeśli chcemy być precyzyjni, rozważmy wydruk pojedynczego znaku jako podstawowej operacji: oznacza to, że aby wydrukować ciąg o długości AK, mamy O(k) .

Ponieważ mamy O (c ^k) możliwe ciągi i dla każdego z nich musimy sprawdzić, czy jest posortowane (z O (k)) i je wydrukować (inne O (k)), całkowita złożoność stała się O (c ^k (k + k)) = O (2c ^k k).

Jednak pomnożenie funkcji dla stałego współczynnika nie zmienia jej złożoności, a zatem odpowiedź pozostaje O (c ^k k).