Czym dokładnie jest algorytm?

Wiem, że może to zabrzmieć trochę po wyjęciu z pudełka, w rzeczywistości zawsze myślałem w środku, ale ostatnio myślałem, być może dlatego, że informatyka zapewnia dużą swobodę, o sposobach opracowywania programów innych niż te nauczane na uniwersytecie.

Rozważ funkcję silni. Zazwyczaj definiujemy tę funkcję jak

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

Nazwałbym to algorytmem i nie mam wątpliwości, że jest to właściwy sposób, aby to zrobić. Następnie zastanawiałem się „czy mogę to zrobić w stałym czasie?”, Co doprowadziło do następującego pomysłu: co jeśli miałbym tablicę liczb całkowitych, gdzie tablica [n] mieści silnię n? Po wypełnieniu tej tablicy mogę po prostu zdefiniować fakt jako:

 int fact(int n) 
 { 
 return array[n]; 
 } 

Nadal nie wydaje mi się, aby algorytm ten działał, mimo że zapewnia poprawny wynik i działa w stałym czasie O (1). Czy można to nazwać algorytmem? W przeciwnym razie dlaczego nie? Mógłbym argumentować, że wypełnienie tablicy wymagałoby pewnego działania algorytmu, nawet jeśli byłby w naszym mózgu, abyśmy mogli wypełnić tablicę, ale czy może to być kryterium? Jak formalnie traktować te aspekty?

Zauważ, że to pojęcie można rozszerzyć na dowolną funkcję działającą na liczbach całkowitych niezależnie od liczby argumentów, musiałbym po prostu użyć macierzy, jeśli funkcja miała 2 argumenty lub 3, jeśli funkcja miała 3 argumenty i tak dalej. Czy te rozwiązania nie są używane tylko ze względu na zużycie pamięci?

Poza tym funkcje mogą obejmować również dowolny program z wyjściem, ponieważ mogłem znaleźć sposób na indeksowanie każdego możliwego wyjścia, które program może zapewnić.

Jako kolejny przykład rozważ wspólne użycie tablicy: początkowo przydzielam tablicę o rozmiarze N, a następnie dodam elementy do tablicy, przechowując wartość o indeksie n i zwiększając n o jedną jednostkę. Następnie, jeśli chcę wyszukać elemento, nie mogę pomóc, ale przeprowadzić liniowe wyszukiwanie w tablicy. Jeśli zamiast tego utworzyłem tablicę wielkości, na przykład Integer.MAXVALUE, do przechowywania liczb całkowitych, zainicjowanych zerami, mógłbym zapisać liczbę całkowitą, umieszczając 1 przy jej indeksie. Następnie mógłbym wyszukać jego istnienie w tablicy w czasie O (1). Co jeśli chciałbym móc umieścić wiele jednostek o tym samym numerze? Nie ma problemu, po prostu zwiększę wartość przechowywaną w indeksie liczb całkowitych.

Sortowanie byłoby nieco bardziej skomplikowane, ale mimo to wyszukiwanie i dodawanie można wykonać w czasie O (1).

Nieformalna definicja algorytmu w popularnym podręczniku wygląda mniej więcej tak:

Algorytm to (1) dobrze zdefiniowana procedura obliczeniowa (2), która wymaga pewnej ilości danych wejściowych i (3) generuje dane wyjściowe (4) dla dobrze określonego problemu obliczeniowego.

W pierwszym przypadku zakodowałeś algorytm, w którym: Problem polega na znalezieniu silni (część 4 definicji), podanej int n jako danych wejściowych (część 2 definicji), kod opisuje obliczenia, które należy wykonać (część 1 definicji ), dane wyjściowe są silnią (część 3 definicji).

W drugim przypadku: Problem polega na znalezieniu elementu tablicy w pozycji n (część 4 definicji), podanej n jako dane wejściowe (część 3 definicji), kod opisuje obliczenia, które należy wykonać (część 2 definicji), wyjście to element w pozycji n (część 1 definicji).

Zapisałeś tam silnię, więc daje ci silnię. Jeśli zapisałeś tam kwadraty lub kostki, dostałbyś kwadraty lub kostki, więc nie można powiedzieć, że drugi fragment sam w sobie jest algorytmem do obliczania silni.

A jeśli powiesz, że tablica przeglądająca się wraz z tablicą mającą f (n) w pozycji n jest algorytmem do obliczania f (n), to zaszedłeś tak głęboko, że nie ma już obliczeń poniżej. Dobrze zdefiniowana procedura obliczeniowa powinna być skończoną informacją. Jeśli nieskończona tablica silni jest częścią procedury obliczeniowej, nie ma to zastosowania. To nie byłby algorytm do obliczania silni.

Mówiąc najogólniej, algorytm to seria kroków do rozwiązania problemu .

W CS powszechnie stosowane / przyjmowane są następujące założenia:

• Algorytm ma skończony opis i dobrze zdefiniowaną procedurę wykonywania swoich kroków w przypadku wystąpienia dowolnego problemu. (Więcej poniżej.)
• Wystąpienie problemu podane jako ciąg skończony (sekwencja symboli wejściowych), a dane wyjściowe algorytmu można zakodować jako ciąg skończony.
• Problem to zbiór wystąpień problemów wraz z możliwymi „poprawnymi” danymi wyjściowymi dla każdego wystąpienia. „Rozwiązywanie” oznacza uzyskanie prawidłowego wyniku.
• (Zwykle) instancje problemowe mogą być dowolnie duże (istnieje nieskończona liczba możliwych instancji, które musi rozwiązać Twój skończony algorytm).

Przed założeniem CS matematycy mieli te same typy problemów, które zgłaszaliście, i wprowadzili formalne definicje obliczeń, aby rozwiązać te problemy. Tak więc obecnie możemy sformalizować wszystkie powyższe założenia, po prostu mówiąc „algorytm to procedura, którą można zaimplementować na maszynie Turinga” . To prawdopodobnie najlepsza formalna odpowiedź na twoje pytanie.

Zauważ, że teza Church-Turinga mówi, że naszym zdaniem nie ma „potężniejszej” formalizacji algorytmów niż Maszyna Turinga.

Przykład silni wchodzi w inny model obliczeń, zwany obliczeniami nierównomiernymi. Maszyna Turinga jest przykładem jednolitego modelu obliczeniowego: ma pojedynczy, skończony opis i działa na dane wejściowe o dowolnie dużych rozmiarach. Innymi słowy, istnieje baza TM, która rozwiązuje problem dla wszystkich rozmiarów wejściowych.

Teraz możemy zamiast tego rozważyć obliczenia w następujący sposób: Dla każdego rozmiaru wejściowego istnieje TM (lub inne urządzenie obliczeniowe), które rozwiązuje problem. To jest zupełnie inne pytanie. Zauważ, że pojedyncza baza TM nie może przechowywać silni każdej pojedynczej liczby całkowitej, ponieważ baza TM ma skończony opis. Możemy jednak stworzyć TM (lub program w C), który przechowuje silnie wszystkich liczb poniżej 1000. Następnie możemy stworzyć program, który przechowuje silnie wszystkich liczb od 1000 do 10000. I tak dalej.

Te niejednorodne typy obliczeń są zwykle modelowane w teoretycznym CS przez obwody. Rozważasz inną konstrukcję obwodu dla każdego możliwego rozmiaru wejściowego.

Niejednorodne modele obliczeń na ogół nie są uważane za algorytmy , nawet jeśli pasują do mojego pierwszego zdania. Powodem jest to, że nie pasują one do naszych kluczowych założeń: nie mają skończonego opisu, który można wdrożyć, aby rozwiązać „cały” problem dla dowolnego rozmiaru danych wejściowych. Potrzebują raczej coraz większego opisu, gdy problem staje się większy (np. Potrzeba większej tabeli odnośników). Są jednak nadal interesującymi modelami obliczeń.

Algorytm to program napisany w C, który powinien działać dla dowolnej długości danych wejściowych (przy założeniu nieskończonej pamięci i nieograniczonych liczb całkowitych). W twoich przykładach, jeśli chcielibyśmy, aby program działał dla wszystkich długości danych wejściowych, wówczas tabela, w której przechowywane są wyniki, byłaby nieskończenie duża; programy w C są zawsze skończone, więc nie można zastosować tego podejścia.

$n!$$n!$) można w nim obliczyć znacznie wydajniej w porównaniu do C.

Martwiąc się o rzeczywiste czasy działania na prawdziwym komputerze, powinniśmy być jeszcze bardziej ostrożni, ale niestety zwykle wykracza to poza granice teoretycznej informatyki.

$n$$n!$

Jakiego pojęcia algorytmu powinniśmy użyć? Jedną z wyżej wymienionych sugestii jest użycie programów C. Możemy to nazwać obliczeniem C. Obliczenia Turinga są tym, co dostajesz, gdy używasz maszyn Turinga. Okazuje się, że funkcja jest obliczalna dla C tylko wtedy, gdy jest obliczalna dla Turinga. W tym sensie oba te modele obliczeń są równoważne. Rzeczywiście, wiele innych modeli jest równoważnych, na przykład wszystkie powszechnie używane języki programowania (przy założeniu nieskończonej pamięci i zmiennych nieograniczonych).

Mówimy, że język programowania P jest kompletny dla Turinga, to funkcja jest obliczalna dla P tylko wtedy, gdy jest obliczalna dla Turinga. Hipoteza Churcha-Turinga jest nieformalnym stwierdzeniem, że wszystkie rozsądne modele obliczeniowe posiadające skończony opis i zajmujące skończony czas są kompletne. Twój model ma skończony opis, ale nie wymaga skończonego czasu.

Ważną częścią wspólnej definicji algorytmu, której brakuje, jest to, że specyfikacja musi być skończona , a rozmiar specyfikacji nie może różnić się w zależności od wielkości danych wejściowych.

Pamięć może być dowolnie duża, podobnie jak dane wejściowe, ale aby być użyteczną definicją algorytmu, przestrzeń kodowa musi być skończona. W przeciwnym razie dostaniesz właśnie zidentyfikowany problem.

$O(\log A)$$A$$O(\log n)$$O(\log n!)$$O(n (\log n)^2)$$s$$n = O(2^s)$$O(2^s~s^2)$$O(1)$

Kilka uwag, które mogą być pomocne:

Problemy stanowią stwierdzenia dotyczące dopuszczalnych danych wejściowych i odpowiadających im danych wyjściowych. Są tym, co chcemy rozwiązać. Algorytmy są procedurami obliczeniowymi. Możemy powiedzieć, że algorytm jest poprawny w odniesieniu do problemu, jeśli akceptuje dane wejściowe, które są dopuszczalne w odniesieniu do problemu i generuje dane wyjściowe zgodnie z opisem problemu.

Oba twoje przykłady są algorytmami, ponieważ oba są procedurami obliczeniowymi wyraźnie. To, czy algorytmy są poprawne, zależy od tego, jak zdefiniujesz problem i jak interpretujesz reprezentację algorytmu. Niektóre stwierdzenia problemów:

1. $n$$n!$
2. $n > 0$$n! <$ INT_MAX$n!$

Niektóre interpretacje pierwszego fragmentu kodu:

1. Jest to pseudokod, który przypomina C / C ++, z wyjątkiem szczegółów. intnaprawdę oznacza na przykład „dowolną liczbę całkowitą”.
2. Należy to interpretować tak, jakby to był prawdziwy program C / C ++.

Interpretacja 1 jest poprawna dla instrukcji problemu 1, o ile silnia przyjmuje wartość 1 dla liczb ujemnych (w przeciwnym razie moglibyśmy zmodyfikować instrukcję problemu, aby ograniczyć domenę lub algorytm, aby uwzględnić pożądane zachowanie). Interpretacja 2 jest poprawna dla opisu problemu 2, z tym samym zastrzeżeniem.

arrayarray$n$$n > 0$$n! <$ INT_MAX$n!$$n < 0$

$n$$n! \geq 2^{32}$$n! \geq 2^{64}$

$k$$k$$n$$kn$$k+n$

Algorytm to program napisany w języku Turing-complete że provably zatrzymanie na wszystkich ważnych komponentów. Wszystkie standardowe języki programowania są kompletne. Słowo to wywodzi się z europejskiego tłumaczenia imienia al-Khwārizmī, perskiego matematyka, astronoma i geografa, którego prace opierały się na dziele hinduskiego matematyka z VII wieku Brahmagupty, który wprowadził indyjski system liczbowy do świata zachodniego.

Pytanie wydaje się zasadniczo dotyczyć tego, czy tabele wyszukiwania są częściami algorytmów. Absolutnie! W maszynach Turinga tabele mogą być kodowane w tabeli stanów TM. TM może zainicjować taśmę na podstawie skończonej ilości danych przechowywanych w tabeli przejścia. Jednak „algorytmy”, które nie działają na nieskończonych wejściach, tylko na wejściach skończonych, są „trywialnymi” maszynami o skończonym stanie (FSM) .

W skrócie : Algorytm jest konstruktywną częścią konstruktywnego dowodu, że dany problem ma rozwiązanie. Motywacją dla tej definicji jest izomorfizm Curry-Howarda między programami i dowodami, biorąc pod uwagę, że program ma interes tylko wtedy, gdy rozwiązuje problem, ale możliwe do udowodnienia. Ta definicja pozwala na więcej abstrakcji i pozostawia pewne drzwi otwarte w odniesieniu do rodzaju domen, które mogą dotyczyć, na przykład w odniesieniu do właściwości skończoności.

Ostrzeżenie . Próbuję znaleźć odpowiednie formalne podejście do odpowiedzi na pytanie. Myślę, że jest to konieczne, ale wydaje się, że żaden z użytkowników, którzy do tej pory odpowiedzieli (w tym ja, a niektórzy byli mniej lub bardziej wyraźnie na ten temat w innych postach), nie ma odpowiedniego tła do prawidłowego opracowania problemów związanych z konstruktywna matematyka, teoria dowodów, teoria typów i takie wyniki, jak izomorfizm Curry-Howarda między dowodami a programami. Robię, co w mojej mocy, tutaj, z wszelkimi fragmentami wiedzy, które posiadam (jak sądzę), i jestem zbyt świadomy ograniczeń tej odpowiedzi. Mam tylko nadzieję, że dam kilka wskazówek, jak według mnie powinna wyglądać odpowiedź. Jeśli zauważysz jakikolwiek punkt, który jest wyraźnie niewłaściwy formalnie (możliwe do udowodnienia), proszę pozwolić mi teraz w komentarzu - lub przez e-mail.

Określanie niektórych problemów

Standardowym sposobem rozważenia algorytmu jest stwierdzenie, że algorytm jest dowolnym, ściśle określonym programem dla niektórych urządzeń komputerowych , w tym również tych, które nie mają żadnych ograniczeń pamięci. Językiem może być również język maszynowy. W rzeczywistości wystarczy rozważyć wszystkie programy dla kompletnego urządzenia komputerowego Turinga (co oznacza brak ograniczeń pamięci). Może nie dać ci wszystkich prezentacji algorytmów, w tym sensie, że algorytmy muszą być wyrażone w formie zależnej w szczegółach od kontekstu interpretacyjnego, nawet teoretycznego, ponieważ wszystko jest zdefiniowane do pewnego kodowania. Ale ponieważ obliczy wszystko, co należy obliczyć, obejmie jakoś wszystkie algorytmy, aż do kodowania.

$\pi$

$\pi$, prawdopodobnie w sensie matematycznym prawie wszystkich. Wymagałoby to jednak większej precyzji w definicjach.

Prawdziwe pytanie brzmi więc, jakie są sensowne algorytmy. Odpowiedź jest taka, że ​​znaczącymi algorytmami są te, które rozwiązują problem, obliczając krok po kroku „rozwiązanie”, „odpowiedź” na ten problem. Algorytm jest interesujący, jeśli jest powiązany z problemem, który rozwiązuje.

Biorąc pod uwagę formalny problem, jak uzyskać algorytm, który rozwiązuje problem. Algorytmy są jawne lub niejawne związane z ideą rozwiązania problemu, co można udowodnić. To, czy nasze techniki dowodowe są dokładne, to inna sprawa, ale staramy się przynajmniej przekonać samych siebie. Jeśli ograniczysz się do matematyki konstruktywnej, co jest właściwie tym, co musimy zrobić (i jest to bardzo akceptowalne ograniczenie aksomatyczne dla większości matematyki), sposobem udowodnienia istnienia rozwiązania jest przejście przez etapy sprawdzające, które faktycznie wykazują konstrukcję który reprezentuje rozwiązanie, w tym ewentualnie inne kroki, które potwierdzają jego poprawność.

Wszyscy programiści myślą coś w stylu: jeśli majstruję przy danych w taki i taki sposób, to otrzymuję ten widget, który ma właściwe właściwości ze względu na twierdzenie Sezamu, i przeprowadzając tę ​​transformację zachowującą foo, otrzymuję pożądaną odpowiedź . Ale dowód jest zwykle nieformalny i nie opracowujemy wszystkich szczegółów, co tłumaczy, dlaczego satelita próbował między innymi okrążyć Marsa pod ziemią (między innymi). Rozważamy większość argumentacji, ale w rzeczywistości zachowujemy tylko konstruktywną część, która buduje rozwiązanie, i opisujemy to w języku komputerowym jako algorytm, który rozwiązuje problem.

Interesujące algorytmy (lub programy)

Wszystko to miało na celu wprowadzenie następujących pomysłów, które są przedmiotem wielu aktualnych badań (których nie jestem specjalistą). Pojęcie „ interesującego algorytmu ” stosowane tutaj jest moje, wprowadzone jako nieformalny symbol zastępczy dla dokładniejszych definicji.

Ciekawy algorytm jest konstruktywną częścią konstruktywnego dowodu, że dany problem ma rozwiązanie . Oznacza to, że dowód musi faktycznie wykazywać rozwiązanie, a nie po prostu udowodnić jego istnienie, na przykład przez zaprzeczenie. Aby uzyskać więcej informacji, zobacz Logika intuicyjna i konstruktywizm w matematyce.

Jest to oczywiście bardzo restrykcyjna definicja, która uwzględnia tylko to, co nazwałem interesującymi algorytmami. Dlatego ignoruje prawie wszystkie z nich. Ale podobnie robią wszystkie nasze podręczniki na temat algorytmu. Próbują uczyć tylko niektórych interesujących.

Biorąc pod uwagę wszystkie parametry problemu (dane wejściowe), krok po kroku informuje, jak uzyskać określony wynik. Typowym przykładem jest rozdzielczość równań ( algorytm nazwy faktycznie pochodzi od imienia perskiego matematyka Muhammada ibna Muszy al-Khwārizmiego , który badał rozdzielczość niektórych równań). Części dowodu służą do ustalenia, że ​​niektóre wartości obliczone w algorytmie mają pewne właściwości, ale te części nie muszą być przechowywane w samym algorytmie.

Oczywiście musi się to odbywać w ramach sformalizowanej ramy logicznej, która określa, z czym są obliczane dane, jakie są dozwolone podstawowe kroki obliczeniowe i jakie są używane aksjomaty.

Wracając do silnego przykładu, można go interpretować jako algorytm, choć trywialny. Normalna funkcja silnia odpowiada dowodowi, że biorąc pod uwagę pewną strukturę arytmetyczną i liczbę całkowitą n, istnieje liczba, która jest iloczynem pierwszych n liczb całkowitych. Jest to dość proste, podobnie jak obliczenia czynnikowe. Może być bardziej złożony w przypadku innych funkcji.

Teraz, jeśli zdecydujesz się na zestawienie silni, zakładając, że możesz, co nie jest prawdą dla wszystkich liczb całkowitych (ale może być prawdą dla niektórych skończonych domen wartości), wszystko, co robisz, to uwzględnienie w swoich aksjomatach istnienia silni przez zdefiniowanie za pomocą nowy aksjomat jego wartość dla każdej liczby całkowitej, abyś już nie musiał niczego udowadniać (a więc obliczać).

Ale system aksjomatów ma być skończony (lub przynajmniej skończony). I istnieje nieskończona liczba wartości dla silni, jedna na liczbę całkowitą. Masz więc problem z skończonym systemem aksjomatów, jeśli aksjatyzujesz funkcję nieskończoną, tj. Zdefiniowaną w domenie nieskończonej. Przekłada się to obliczeniowo na fakt, że twoje przyszłe wyszukiwanie tabeli nie może być zaimplementowane dla wszystkich liczb całkowitych. To zabiłoby zwykły wymóg skończoności dla algorytmów (ale czy ma być tak rygorystyczny, jak często jest przedstawiany?).

Możesz zdecydować się na zdefiniowany generator aksjomatów do obsługi wszystkich przypadków. Oznaczałoby to mniej więcej włączenie standardowego programu silniakowego do algorytmu w celu zainicjowania tablicy w razie potrzeby. Nazywa się to zapamiętywaniem przez programistów. Jest to faktycznie najbliższy odpowiednik wstępnie obliczonej tabeli. Można zrozumieć, że ma wstępnie obliczoną tabelę, z wyjątkiem faktu, że tabela jest faktycznie tworzona w leniwym trybie oceny , gdy jest to potrzebne. Ta dyskusja prawdopodobnie wymagałaby nieco bardziej formalnej opieki.

Możesz zdefiniować swoje prymitywne operacje według własnego uznania (w ramach zgodności z formalnym systemem) i przypisać im dowolne koszty wybrane podczas korzystania z algorytmu, aby przeprowadzić analizę złożoności lub wydajności. Ale jeśli konkretne systemy, które faktycznie implementują twój algorytm (na przykład komputer lub mózg) nie są w stanie spełnić tych specyfikacji kosztów, twoja analiza może być interesująca intelektualnie, ale jest bezwartościowa do rzeczywistego wykorzystania w prawdziwym świecie.

$2^{1000}$

Jakie programy są interesujące

Ta dyskusja powinna być lepiej powiązana z wynikami, takimi jak izomorfizm Curry-Howarda między programami i dowód. Jeśli jakikolwiek program jest faktycznie dowodem czegoś, każdy program może być interpretowany jako interesujący program w rozumieniu powyższej definicji.

Jednak, według mojego (ograniczonego) zrozumienia, ten izomorfizm jest ograniczony do programów, które można dobrze pisać w odpowiednim systemie pisania, gdzie typy odpowiadają twierdzeniom teorii aksjomatycznej. Dlatego nie wszystkie programy można zakwalifikować jako interesujące programy. Domyślam się, że w tym sensie algorytm powinien rozwiązać problem.

Prawdopodobnie wyklucza to większość „losowo generowanych” programów.

Jest to również nieco otwarta definicja „interesującego algorytmu”. Każdy program, który można uznać za interesujący, jest zdecydowanie taki, ponieważ istnieje zidentyfikowany system typów, który sprawia, że ​​jest interesujący. Ale program, który do tej pory nie był dostępny do pisania, może stać się do pisania z bardziej zaawansowanym systemem typów, a tym samym stać się interesujący. Mówiąc dokładniej, zawsze było to interesujące, ale z powodu braku wiedzy na temat właściwego systemu typów nie mogliśmy go poznać.

Wiadomo jednak, że nie wszystkie programy można pisać, ponieważ wiadomo, że niektóre wyrażenia lambda, takie jak implementacja kombinatora Y , nie mogą zostać wpisane w systemie typu dźwięku .

Ten widok dotyczy tylko formalności programistycznych, które można bezpośrednio powiązać z jakimś systemem dowodu aksjomatycznego. Nie wiem, jak można ją rozszerzyć na formalizacje obliczeniowe niskiego poziomu, takie jak Maszyna Turinga. Ponieważ jednak algorytm i obliczalność to często gra polegająca na kodowaniu problemów i rozwiązań (pomyśl o arytmetyki zakodowanej w rachunku lambda ), można wziąć pod uwagę, że każde formalnie zdefiniowane obliczenie, które można przedstawić jako kodowanie algorytmu, jest również algorytmem. Takie kodowania prawdopodobnie wykorzystują tylko bardzo niewielką część tego, co można wyrazić w formalizmie niskiego poziomu, takim jak Maszyny Turinga.

Jednym z zainteresowań tego podejścia jest to, że daje ono pojęcie algorytmu, które jest bardziej abstrakcyjne i niezależne od kwestii faktycznego kodowania, „fizycznej reprezentacji” dziedziny obliczeniowej. Można więc na przykład rozważyć domeny z nieskończonymi obiektami, o ile istnieje obliczeniowy sposób ich użycia.

W chwili pisania nie ma dobrej formalnej definicji „algorytmu”. Jednak pracują nad tym mądrzy ludzie.

Wiemy, że czymkolwiek jest „algorytm”, znajduje się gdzieś pomiędzy „funkcją matematyczną” a „programem komputerowym”.

Funkcja matematyczna to formalne pojęcie odwzorowania od danych wejściowych do wyników. Na przykład „sort” to odwzorowanie między sekwencją uporządkowanych elementów a sekwencją uporządkowanych elementów tego samego typu, która odwzorowuje każdą sekwencję na jej uporządkowaną sekwencję. Ta funkcja może być zaimplementowana przy użyciu różnych algorytmów (np. Sortowanie według scalania, sortowanie na stosie). Każdy algorytm z kolei można zaimplementować przy użyciu różnych programów (nawet w tym samym języku programowania).

Najlepszym sposobem, w jaki rozumiemy, czym jest „algorytm”, jest to, że jest to pewnego rodzaju klasa równoważności w programach, gdzie dwa programy są równoważne, jeśli robią „zasadniczo to samo”. Wszelkie dwa programy, które implementują ten sam algorytm, muszą obliczać tę samą funkcję, ale odwrotność nie jest prawdą.

Podobnie istnieje klasa równoważności między algorytmami, gdzie dwa algorytmy są równoważne, jeśli obliczają tę samą funkcję matematyczną.

Trudność w tym wszystkim polega na uchwyceniu tego, co rozumiemy przez „zasadniczo to samo”.

Jest kilka oczywistych rzeczy, które powinniśmy uwzględnić. Na przykład dwa programy są zasadniczo takie same, jeśli różnią się tylko zmiennymi nazwami. Większość modeli języków programowania ma natywne pojęcia „równoważności” (np. Redukcja beta i konwersja eta w rachunku lambda), dlatego też powinniśmy je wrzucić.

Niezależnie od wybranej przez nas relacji równoważności daje nam to pewną strukturę. Algorytmy tworzą kategorię, ponieważ są kategorią ilorazową programów. Niektóre interesujące równoważne relacje powodują powstanie interesujących struktur kategorycznych; na przykład kategoria pierwotnych algorytmów rekurencyjnych jest uniwersalnym obiektem w kategorii kategorii. Ilekroć zobaczysz taką interesującą strukturę, wiesz, że ta linia pytań prawdopodobnie będzie przydatna.

Twoje pytanie i opis nie odnoszą się tak bardzo. Algorytm jest teoretyczny i nie dotyczy żadnego języka programowania. Algorytm to zestaw reguł lub kroków (procedur) mających na celu rozwiązanie problemu. Twój problem można rozwiązać na wiele sposobów lub za pomocą wielu algorytmów.

Twoje drugie rozwiązanie oznacza najpierw obliczenie dużej liczby silni, które początkowo zajmą dużo czasu, a następnie je zapiszą. Zużyje więcej pamięci, ale ostatecznie będzie szybszy, podczas gdy pierwszy nie zużywa pamięci, ale zużywa moc obliczeniową, więc będziesz musiał wybrać w zależności od środowiska.