Algorytm Karacuby
Z Wikipedii, wolnej encyclopedia
Algorytm Karacuby – algorytm szybkiego mnożenia dużych liczb całkowitych, opracowany przez Anatolija Karacubę w 1960 i opublikowany razem z Jurijem Ofmanem w 1962[1][2][3] roku. Jego złożoność obliczeniowa wynosi Θ w przypadku mnożenia dwóch liczb składających się z n cyfr. Jest on zatem szybszy od algorytmu klasycznego dla odpowiednio dużych wartości n. Mnożenie niewielkich liczb jest szybsze przy pomocy mniej skomplikowanego algorytmu klasycznego.
Szybkie fakty Rodzaj, Struktura danych ...
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Zamknij