Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Zloznosc algortymu - notacja Wielkie O

greep 13 Maj 2010 00:58 2090 2
  • #1 13 Maj 2010 00:58
    greep
    Poziom 19  

    Czy ktos moze mi potwierdzic, ze dobrze obliczylem notacje "Wielkie O" dla ponizszego algorytmu:

    Moj algortym wyszukuje wszystkie mozliwe przedrostki wyrazow na podstawie ilosci wcisnietych klawiszy telefonu komorkowego.
    Na klawiaturze telefonu komorkowego mamy 8 przyciskow z literkami.
    Wszystkich literek jest 26, tak wiec na kazdy klawisz przypada srednio 3,25 literki.

    Czyli np: dla wcisnietego jednego klawisza k=1 , program generuje 3^1 = 3 przedrostki.
    Dla wcisnietych dwoch klawiszy k= 2, program generuje 3^2 = 9 przedrostow.


    Jesli np: najdluzszy wyraz ma ‘n’ liter, to wygenerujemy (3,25)^n przedrostkow.
    Chcac wyrazic to za pomoca notacji Wielkie O, otrzymamy O( (3,25)^n ) czyli zlozonosc wykladnicza, najgorsza z mozliwych...
    Czy mam racje?

    Taka zlozonosc w przypadku mojego algorytmu jest do zaakceptowania, bo pomimo iz jest wykladnicza, nie bedzie rosla w nieskonczonosc (Maksymalne 'n', bedzie dlugosci najdluzszego wyrazu).
    Ale... to nie zmienia faktu, ze zloznosc jest wykladnicza: O( (3,25)^n ).
    Czy mam racje???

    0 2
  • #2 13 Maj 2010 11:24
    lpm11
    Poziom 22  

    3,25 to uproszczenie. Ale jeżeli je przyjmiemy to masz rację.
    Jeżeli chcesz wygenerować te wszystkie słowa aby je np. wypisać, to nie jesteś w stanie zbić tej złożoności.
    To czy zaakceptujesz tą złożoność to już twoja sprawa, zależy co chcesz zrobić:)

    0
  • #3 13 Maj 2010 13:23
    greep
    Poziom 19  

    dzieki za odpowiedz.
    to jaka w takim razie bylaby zlozonosc 'bez uproszczenia'?

    Ponizej implementacja rekursywnej metody, ktora generuje wszystkie przedrostki wrazow:

    Code:

    149     private static Collection<String> lettersCombinations(int n, String prefix, List<String> list) {
    150         if (_keys.size() > 0) {
    151             List<Character> chars = _keyMap.get(_keys.get(n));
    152
    153             for (int i = 0; i < chars.size(); i++) {
    154                 char c = chars.get(i);
    155
    156                 if (n + 1 < _keys.size()) {
    157                     lettersCombinations(n + 1, prefix + c, list);
    158                 }
    159                 else {
    160                     list.add(prefix + c);
    161                 }
    162             }
    163         }
    164         
    165         return list;
    166     }

    0