W jaki sposób możemy zmodyfikować prawie każdy algorytm, aby uzyskać najlepszy czas działania w najlepszym przypadku?

To jest pytanie od wprowadzenia do algorytmów przez Cormen. Ale to nie jest zadanie domowe, zamiast samokształcenia.W jaki sposób możemy zmodyfikować prawie każdy algorytm, aby uzyskać najlepszy czas działania w najlepszym przypadku?

Dużo myślałem i szukałem w google. Odpowiedź, którą mogę wymyślić to: -

Użyj innego algorytmu.
Daj najlepiej przypadek wejścia
Użyj lepszy komputer, aby uruchomić algorytm

Ale nie sądzę, są prawidłowe. Zmiana algorytmu nie jest taka sama jak w przypadku, gdy algorytm ma lepszą wydajność. Również użycie lepszego komputera może zwiększyć prędkość, ale algorytm nie jest lepszy. To jest pytanie na początku książki, więc myślę, że to jest coś prostego, co przeoczam.

W jaki sposób możemy zmodyfikować prawie każdy algorytm, aby uzyskać najlepszy możliwy czas działania?

Źródło

2013-08-07 Aseem Bansal

Algorytmy mieć najlepszy, średni i najgorszych przypadków działa razy. Nie można utworzyć algorytmu, który ma najlepszy czas działania, ponieważ i tak istnieje. Być może masz na myśli _improve_ jego najlepszy czas działania? Proszę napisać dokładne pytanie z książki. P.S. Szybkość komputera nie wpływa na kolejność czasu algorytmu. – Shahbaz

Po tych liniach, wyobrażam sobie, że najlepszy czas działania można osiągnąć poprzez wprowadzenie zerowej długości: D – AdamKG

@Shahbaz Wiem o tym. To też mnie zdezorientowało. Ale tytuł pytania to dokładne sformułowanie z książki CLRS. Słyszałem wiele pochwał dla tej książki, więc nie sądzę, że stwierdzenie może być błędne. –

Możesz zmodyfikować dowolny algorytm, aby uzyskać najlepszą możliwą złożoność czasu w przypadku O(n), dodając specjalny przypadek, że jeśli dane wejściowe pasują do tego szczególnego przypadku, zwróć buforowaną odpowiedź zakodowaną na sztywno (lub inną łatwo uzyskaną odpowiedź).

Na przykład dla dowolnego sortowania można zrobić najlepszy przypadek O(n), sprawdzając, czy tablica jest już posortowana - a jeśli tak, zwróć ją w niezmienionym stanie.

Należy zauważyć, że nie ma to wpływu na średnie lub najgorsze przypadki (zakładając, że nie są one lepsze niż O(n)) i zasadniczo poprawia się złożoność algorytmu w najlepszym przypadku.

Uwaga: Jeśli wielkość wejścia jest ograniczona, to samo optymalizacji robi najlepsze sprawę O(1), ponieważ czytanie wejście w tym przypadku jest O(1).

Źródło

2013-08-07 12:50:29 amit

O ile ta granica nie jest zakodowana na sztywno w algorytmie (o którym nigdy nie słyszałem) '(1)', w naszym obecnym wszechświecie wszystkie aplikacje ograniczyły wejście. Zatem fakt, że nie można podać algorytmowi większej ilości liczb, nie spowoduje, że O (1). '(1)' Na przykład 'sum = 0; dla i = 0 do 100: sum + = array [i]; 'jest algorytmem O (1), ale oczywiście w algorytmie nie ma żadnych rozmiarów kodu. – Shahbaz

@Shahbaz Chociaż zgadzam się z koncepcją teoretyczną, tak - jeśli algorytm ma ograniczone wejście, to jest ostateczny zestaw wejść, a więc ostateczny zestaw możliwych przebiegów, a rozwiązaniem jest 'O (1)' (ograniczony przez najdłuższy z nich), pomysł polegał na tym, że jeśli twoje wejście ma intencję 32-bitową, to jest to 'O (1)', ale iterowanie po nim od 1 do 'n 'jest zwykle uważane za' O (n) ', chociaż teoretycznie jest to rzeczywiście "O (1)". – amit

Byłem przeciwny do twojego ostatniego zdania, mówiąc, że algorytmem będzie O (1), jeśli ma ograniczone wejście. Mówiłem tylko, że zasadniczo nie ma algorytmu, który mówi: "Akceptuję tylko dane wejściowe ograniczone przez tak wiele". Teoretycznie są _nie_ O (1). Praktycznie wszystkie algorytmy na tym świecie to O (1). Krótko mówiąc, to zdanie jest bezużyteczne. – Shahbaz

Gdybyśmy mogli wprowadzić instrukcję dla tego właśnie algorytmu w modelu obliczeniowym samego systemu, możemy po prostu rozwiązać problem w jednej instrukcji.

Ale jak można już odkryć, jest to wysoce nierealistyczne podejście. Tak więc ogólna metoda modyfikacji dowolnego algorytmu mającego najlepszy czas działania jest prawie niemożliwa. Co możemy zrobić w max to zastosowanie usprawnień w algorytmie do ogólnych zwolnień znalezionych w różnych problemach.

Lub możesz przejść naiwnie, biorąc najlepsze dane wejściowe sprawy. Ale znowu to nie modyfikuje algorytmu. W rzeczywistości wprowadzenie algorytmu w samym systemie obliczeniowym, zamiast być wysoce nierealne, nie jest modyfikacją algorytmu.

Źródło

2015-07-23 07:20:28

Drogi możemy zmodyfikować algorytm mieć najlepszym przypadku czas pracy to:

Jeżeli algorytm jest w miejscu jego zastosowania/rozwiązania, ex, dla coraz większej sortowania , jest to już sortowanie rosnąco i tak dalej.

Jeśli zmodyfikować algorytm tak, że mamy wyjścia i wyjścia dla jego celów tylko dlatego zmusza wiele pętli zagnieżdżonych być tylko jeden

Źródło

2017-06-16 14:53:02

W jaki sposób możemy zmodyfikować prawie każdy algorytm, aby uzyskać najlepszy czas działania w najlepszym przypadku?

Odpowiedz

Powiązane problemy