Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 08. 12. 2022 20:49

<h1>dydy</h1>
Příspěvky: 150
Reputace:   
 

složitost konkrétního algoritmu - správnost

Je správné určení složitosti tohoto algorimtu?
Prvočíselný rozklad (je tam i ukázka kódu)
"rozkládané číslo postupně zkoušet dělit všemi prvočísly. Tento algoritmus je sice jednoduše pochopitelný a implementovatelný, jeho složitost je ale exponenciální"
zjednodušeně:
for prvocislo in prvocisla: // cislo je počáteční vstup
    while cislo % prvocislo == 0:
      rozklad.append(prvocislo)
      cislo /= prvocislo

Za mě je tento algoritmus lineární.

Nebo je rozdíl v tom upřesnění termínů? Vzhledem k hodnotě vstupu a nebo vzhledem k délce vstupu ? (Délka čísla jakožto počet číslic, což je logaritmus hodnoty  o příslušném základu, obráceně: hodnta čísla s počtem číslc roste exponenciálně). Tudíž pokud to otočíme, že vstupem se myslí délka, pak je vztah složitostí, že složitost vzhledem k hodnotě je nutné umocnit.

V tomto konkrétním případě z lineární funkce  y(x)=x se stane y'(x)=e^x.

A konkrétně, kde tady je ta linearita? (nebo se tím myslí i víc-nebo-rovno linearita)? Je to  skryté v funkci modulo  nebo v cyklu while? 

Jak bývá implementované modulo? Pochybuji že jako smyčka odečítání (while dělenec)>dělitel, ale jako reálné (celočíselné) dělení a odečet originálu o zpětného vynásobení...   

Praktický dotaz, z mého pozorování  se složitostí myslí právě vzhledem k délce hodnoty a ne k hodnotě samotné. Jaké je pro to vysvětlení nebo důvod?

Offline

 

#2 08. 12. 2022 21:03

MichalAld
Moderátor
Příspěvky: 4764
Reputace:   125 
 

Re: složitost konkrétního algoritmu - správnost

To se dokonce nějak jmenuje, jestli "pseudolineární složitost" či tak něco.

Protože lineárně rostoucí výpočetní náročnost to má jen když to N je velikost toho čísla. Ale pokud N je velikost jeho reprezentace (třeba počet bitů, které to číslo reprezentují), roste to samozřejmě exponenciálně.


Proč se to dělá tak a né jinak?
No, třeba když se vymýšlí šifry, tak je výpočetní náročnost případného prolomení šifry klíčová věc pro posouzení její použitelnosti. A protože z našeho technického hlediska je "lineární" přidávání dalších bitů (použití 128 bitů namísto 64 bitů pro nás znamená jen dvojnásobnou složitost, zatímco pro případného hackera [mathjax]2^{64}[/mathjax] násobnou složitost prolomení)

Offline

 

#3 08. 12. 2022 22:55 — Editoval Aleš13 (08. 12. 2022 23:02)

Aleš13
Příspěvky: 328
Reputace:   
 

Re: složitost konkrétního algoritmu - správnost

<h1>dydy</h1> napsal(a):

Jak bývá implementované modulo? Pochybuji že jako smyčka odečítání (while dělenec)>dělitel, ale jako reálné (celočíselné) dělení a odečet originálu o zpětného vynásobení...

Modulo je vedlejší výsledek celočíselného dělení. Když počítám C = A div B, tak shiftnu B tolikrát doleva, až je větší než A. Pak ve smyčce odčítám B od A. Když vyjde záporné číslo, zase to přičtu zpátky, když ne, nahodím nejnižší bit C. Pak shiftnu C doleva a B doprava a opakuju dokud nemá B svou původní hodnotu. V C mám podíl, v A zbytek.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson