Matematické Fórum

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?