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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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 02. 05. 2018 15:25 — Editoval liamlim (02. 05. 2018 15:37)

liamlim
Příspěvky: 214
Škola: MFF UK
Pozice: student
Reputace:   
 

Pomoc s casovou slozitosti

EDIT: vím, že algoritmus je neefektivní. Chtěl bych si tu časovou složitost vyjádřit jen jako cvičení :)

EDIT2: Mým cílem pak je odstranit člen $n^{1/2}$ přidáním nějakého rychlého algoritmu, který určí třeba dělitele v rozmezî $n^{2/5}$$n^{3/5}$ nebo tak nějak. To ale jen věci dál komplikuje, protože neumím přesně určit zatím ani složitost tohoto jednoduchého a neefektivního algoritmu.

Ahoj! Potřeboval bych pomoct s výpočtem časové složitosti následujícího algoritmu:


1) Vyzkoušíme všechny dělitele čísla $n$ až po $n^{1/3}$. To zjevně zvládneme v $O(n^{1/3})$. Jestli jsme našli dělitel, jsme hotovi. Jinak jdeme na (2).

2) Menší dělitel označme $p$. Můžeme jej odhadnout: $n^{1/3} < p < n^{1/2}$. Větší dělitel označme $q$. Můžeme jej odhadnout: $n^{1/2} < q < n^{2/3}$. Odtud plyne, že: $n^{1/3} + n^{1/2} < p + q < n^{1/2} + n^{2/3}$. Hodnota $p+q$ tedy může nabývat nejvýše $n^{2/3} - n^{1/3}$ hodnot, což je $O(n^{2/3})$. Každou z těchto možných hodnot postupně dosaďme do $a$ a jděme na (3).

3) Řešme kvadratickou rovnici $p^2 - ap + n = 0$. Pokud je kořen $p$ přirozené číslo, končíme.


Můj problém je, že zatím nejsem schopný odhadnout, jak nejrychleji je možné bod (3) provést. Ta hodnota mi pořád jaksi závisí na $a$ a vůbec si nejsem jistý výsledkem vzniklé sumy. Něco nejspíš dělám špatně... Za jakékoliv postrčení bych byl vděčný.

Offline

 

#2 02. 05. 2018 15:43

check_drummer
Příspěvky: 2540
Reputace:   66 
 

Re: Pomoc s casovou slozitosti

↑ liamlim:
Ahoj, těch hodnot a máš $O(n^{2/3})$ a každou takovou rovnici jsi schopen vyřešit v konstantním čase - nebo ne?
Resp. v jakém čase jsi schopen spočítat operace s čísly velkými jako n - v konstantním nebo v log(n)? Pak by ta šložitost byla $O(log(n).n^{2/3})$


Nikdy nechibuji.

Offline

 

#3 02. 05. 2018 15:55

laszky
Příspěvky: 798
Škola: MFF UK, FJFI CVUT
Reputace:   50 
 

Re: Pomoc s casovou slozitosti

↑ liamlim:

Jinak pokud zkousis na zacatku vsechny delitele az po $n^{1/3}$, potom zkousis jenom prvocisla (ostatni nema smysl), takze ta slozitost bude lepsi $\mathcal{O}\left(\frac{n^{1/3}}{\log n}\right)$

Offline

 

#4 02. 05. 2018 16:08 — Editoval liamlim (02. 05. 2018 16:10)

liamlim
Příspěvky: 214
Škola: MFF UK
Pozice: student
Reputace:   
 

Re: Pomoc s casovou slozitosti

↑ check_drummer:

Já teď něčemu úplně nerozumím. Jak umím konstantně vyřešit kvadratickou rovnici? Buď potřebuji odmocninu, která má časovou složitost logaritmickou nebo nějaké půlení intervalů, které taky není konstantní, ne?

edit: No a já právě nevím, jaký je nejlepší možný přístup. Navíc $a$ má celkem nepěkné meze a vystupuje v sumě, což mi komplikuje určení, co bude nejlepší.

Offline

 

#5 02. 05. 2018 22:40 — Editoval check_drummer (02. 05. 2018 22:47)

check_drummer
Příspěvky: 2540
Reputace:   66 
 

Re: Pomoc s casovou slozitosti

↑ liamlim:
Ale logaritmus je celkem malý faktor vzhledem k tomu $O(n^{2/3})$. Odmocnina by se dala za ten logaritmus zvládnout. Ale složitost log(n) bude mít i sčítání nebo násobení...
Záleží totiž jestli uvažuješ n takové, že sčítání dvou čísel velikosti n považuješ za konstantní a nebo ne. Pokud ne, tak tam bude ten faktor log(n).


Nikdy nechibuji.

Offline

 

#6 02. 05. 2018 22:42

check_drummer
Příspěvky: 2540
Reputace:   66 
 

Re: Pomoc s casovou slozitosti

↑ laszky:
Ahoj, ale jak zjistíš rychle, že je dané číslo prvočíslem? Pokud podle tabulek, tak to mohu tabulku použít i pro n. :-)


Nikdy nechibuji.

Offline

 

#7 02. 05. 2018 23:14

laszky
Příspěvky: 798
Škola: MFF UK, FJFI CVUT
Reputace:   50 
 

Re: Pomoc s casovou slozitosti

↑ check_drummer:

Kdyz postupujes od zacatku, tak to neni problem, proste zkontrolujes delitelnost dvema a vyradis vsechna suda cisla, pak zkontrolujes delitelnost tremi a vyradis nasobky tri, pak uz nekontrolujes delitelnost 4, ale jdes rovnou na delitelnost 5 atd ;-)

Offline

 

#8 02. 05. 2018 23:27

liamlim
Příspěvky: 214
Škola: MFF UK
Pozice: student
Reputace:   
 

Re: Pomoc s casovou slozitosti

↑ laszky:

To úplně nefunguje. Stejně budeš muset všechna čísla vzít alespoň jednou do ruky. Nějak je označit nebo tak něco. To zabere konstantní čas stejně jako prosté vydělení a ověření zda se nejedná o dělitel.

Offline

 

#9 03. 05. 2018 20:37

check_drummer
Příspěvky: 2540
Reputace:   66 
 

Re: Pomoc s casovou slozitosti

↑ laszky:
Když proškrtáváš násobky dvou, tří, atd. tak stejně nakonec musíš projít všechna čísla a ne jen prvočísla...
Možná tím nějaký čas ušetříš, ale asymptoticky asi ne.


Nikdy nechibuji.

Offline

 

#10 03. 05. 2018 22:10

laszky
Příspěvky: 798
Škola: MFF UK, FJFI CVUT
Reputace:   50 
 

Re: Pomoc s casovou slozitosti

↑ check_drummer:

No, ma uvaha byla nasledujici:

Kdyz budu brat v uvahu pouze cisla $2$, $2k+1$ pro $k\in\mathbb{N}$ snizim casovou slozitost na polovinu.

Pokud budu brat v uvahu pouze cisla $2$, $3$, $6k-1,6k+1$ pro $k\in\mathbb{N}$ snizim ji na tretinu, atd.

Pokud na zacatku takto vyradim nasobky $C\log n$ prvocisel, ziskam  $\mathcal{O}\left(\frac{n^{1/3}}{\log n}\right)$.

Vidim v tom pouze praci navic v pocatecnim stanoveni tech omezujicich podminek.

Ale urcite tim nechci liamlimovi branit v testovani sudych cisel ;-)

Offline

 

#11 03. 05. 2018 23:23

MichalAld
Příspěvky: 856
Reputace:   23 
 

Re: Pomoc s casovou slozitosti

Co vlastně má být cílem toho algoritmu? Test prvočíselnosti nebo rozklad na prvočísla (faktorizace) ?

Taky jsem narazil na to, že pokud ono "n" je hodnota (a né třeba počet bitů jež číslo reprezentují) jedná se stejně fakticky o asymptoticky exponenciální složitost.

Viz: Pseudopolynomická časová složitost

Offline

 

#12 04. 05. 2018 00:02

liamlim
Příspěvky: 214
Škola: MFF UK
Pozice: student
Reputace:   
 

Re: Pomoc s casovou slozitosti

↑ MichalAld:

Já si jen pohrával s nějakými rovnostmi a zjistil jsem, že mám problém s vyjádřením té složitosti. Ten algoritmus je nanic, je pomalý. Najde nějaký dělitel zadaného čísla.

Offline

 

#13 05. 05. 2018 22:42

check_drummer
Příspěvky: 2540
Reputace:   66 
 

Re: Pomoc s casovou slozitosti

↑ laszky:
Ahoj, ale pokud předem vyžřadíš nějaké násobky prvočísel, tak jednak ta prvočísla musíš znát a jednak musíš mít nějaký rozumný způsob jak zajistit, že jejich násobky vůbec nebudeš zkoumat: Pokud bys např. postupoval tak, že pojedeš v cyklu přes přirozená čísla a u každého se zeptáš, zda je násobkem nějakého z uvedených prvočísel, tak časovou složitost nesnížíš, protože na každém čísle strávíš konstantně mnoho času - minimálně abys ověřil, že dané číslo nemáš dále testovat.


Nikdy nechibuji.

Offline

 

#14 05. 05. 2018 22:56 — Editoval laszky (05. 05. 2018 23:05)

laszky
Příspěvky: 798
Škola: MFF UK, FJFI CVUT
Reputace:   50 
 

Re: Pomoc s casovou slozitosti

↑ check_drummer:

Ok. Tak jednoducha otazka: Usetrim cas, kdyz zkontroluju dvojku a pak uz jenom cisla $2k+1$, $k\in\mathbb{N}$? Ja se na ta suda cisla vubec nebudu ptat, proste je preskocim ;-)

Offline

 

#15 05. 05. 2018 23:14 — Editoval liamlim (05. 05. 2018 23:17)

liamlim
Příspěvky: 214
Škola: MFF UK
Pozice: student
Reputace:   
 

Re: Pomoc s casovou slozitosti

↑ laszky:

Ano. To čas skutečně ušetří, ale ne asymptoticky. Zrychlení o polovinu je super, ale nemůže celkovou asymptotickou složitost ovlivnit. Aby to ovlivnilo asymptotickou složitost, bylo by třeba takto vyřadit násobky nekonstantně mnoha prvočísel. Třeba i málo jako $\log n$. To ale pro změnu znamená, že je třeba předem nekonstantně prvočísel znát, což pro dost velké $n$ nutně nemůžeme.

pozn.: Asi bych měl dodat, že se tím algoritmem v tomto vláknu už nezabývám. Našel jsem si zase další věci, které mi připadají zajímavější. Navíc ten postup co jsem plánoval dle mého názoru nemůže fungovat.

Offline

 

#16 06. 05. 2018 01:35 — Editoval laszky (06. 05. 2018 01:36)

laszky
Příspěvky: 798
Škola: MFF UK, FJFI CVUT
Reputace:   50 
 

Re: Pomoc s casovou slozitosti

↑ liamlim:

Podle wiki je nejvetsi zname prvocislo $2^{77,232,917}-1\approx 10^{23,249,425}$, tabelovano jsem narychlo nasel prvocisla az do $10^{12}\gg23,249,425$, tj az do 1000 miliard = 1 bilionu. ;-) Takze v tomto neni zadny prakticky problem.

Offline

 

#17 06. 05. 2018 08:54

check_drummer
Příspěvky: 2540
Reputace:   66 
 

Re: Pomoc s casovou slozitosti

↑ laszky:
Jak píše kolega - tím dosáhneš jen zrychlení o konstantu a nebude to mít vliv na asymptotickou složitost.
V praxi je velmi dobré, když program neběží třeba 10 hodin, ale jen hodinu, ale tady jsme v teoretické rovině a zrychlení o konstantu nás (vulgárně řečeno) nezajímá.


Nikdy nechibuji.

Offline

 

#18 07. 05. 2018 00:52

MichalAld
Příspěvky: 856
Reputace:   23 
 

Re: Pomoc s casovou slozitosti

laszky napsal(a):

↑ liamlim:

Podle wiki je nejvetsi zname prvocislo $2^{77,232,917}-1\approx 10^{23,249,425}$, tabelovano jsem narychlo nasel prvocisla az do $10^{12}\gg23,249,425$, tj az do 1000 miliard = 1 bilionu. ;-) Takze v tomto neni zadny prakticky problem.

No ale $10^{12}$ není žádné velké číslo, to je nějakých 40 bitů, to v dnešní době 64-bitových počítačů ani nestojí za řeč, to není ani jeden registr v procesoru...

To největší známé prvočíslo je už dost velké, na jeho uložení by bylo třeba nějakých 77 Mb, ale to je dnes taky celkem prd...každopádně ale, to jsou dost speciální čísla (Mersennova čísla) u kterých to lze rychle vyzkoušet.
Neznamená to ovšem, že bychom znali (nebo dokázali najít) i všechna mezi tím - tam je obrovské neznámé území.

Kdyby nebyl praktický problém s nalezením nějakého dělitele velkého čísla, nebyl by praktický problém i s "lámáním" RSA šifry. Tam se dnes používají čísla o délce 1024 bitů nebo 4096 bitů (což je o dost více než těch 40, co máme tabelovaných).

Na druhou stranu, kvantové počítače (pokud je někdy někdo vyrobí) by faktorizaci měly zvládat v polynomiálním čase - i když jsem zatím úplně nepochopil, jak to dělají.

Offline

 

#19 07. 05. 2018 03:41

laszky
Příspěvky: 798
Škola: MFF UK, FJFI CVUT
Reputace:   50 
 

Re: Pomoc s casovou slozitosti

↑ MichalAld:

Myslim, ze si nerozporujeme. Pokud to z toho komentare nebylo videt, tak to melo znamenat, ze $23,249,425\approx \log_{10} 2^{77,232,917}$ neni vubec zadne velke cislo, jelikoz minimalne $10^{12}$ prvocisel je urcite tabelovano. Takze dosahnout v praktickem vypoctu toho faktoru $1/\log n$ (=vyrazeni $\log n$ prvocisel a jejich nasobku) by nemel byt problem. Na druhou stranu, prvocisla se urcite hledaji uplne jinak, takze to slovo "prakticky" se musi brat v uvozovkach :-)  (A samozrejme maji pravdu i ↑ check_drummer: ↑ liamlim:, ze to neni az tak moc asymptoticky odhad - spis "prakticky" asymptoticky :-) )

Offline

 

#20 09. 05. 2018 14:57

check_drummer
Příspěvky: 2540
Reputace:   66 
 

Re: Pomoc s casovou slozitosti

↑ laszky:
Je tam rozpor pokud se týká asymptotické složitosti, tj. chování "v nekonečnu" - tam už žádnou tabelaci použít nemůžeš a proto nemůžeš říci, že znáš řekněme log(n) prvočísel. Korektní by bylo použít třeba log(m) prvočísel, kde ale m je vzheldem k n konstantní.
Teď jsem si všiml Tvé poznámky o "praktické asymptotice", tak to je potom ok.

Ale zbývá tam jeden problém - pokud předem znám prvočísla, která budu testovat, tak můžu stanovit, že budu třeba procházet jen lichá čísla, nebo jen čísla tvaru 6k+-1 (budu ignorovat násobky 2 a 3), ale pokud ta prvočísla předem neznám, tak si myslím že nebudu schopen apriori zjistit jaká čísla mám procházet a jaká ignorovat.  I když - možná pomocí čínské věty o zbytcích najdu vhodná čísla tvaru Xk+Yi...


Nikdy nechibuji.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson