Complessità
Come faccio a determinare una stima per il numero di operazioni bit necessarie per calcolare $ [√(k^k) (mod T)] $ con T $ <= k^3 $ ?
Io so che la complessità del calcolo a(mod n) è O (loga * logn) e se lavoro su un fissato intero n, la complessità è O(loga)
ma in questo caso come posso fare?
Io so che la complessità del calcolo a(mod n) è O (loga * logn) e se lavoro su un fissato intero n, la complessità è O(loga)
ma in questo caso come posso fare?
Risposte
e comunque la complessità di un numero es: m^n = O $ (n^2logm+mlogn) $
solo non riesco a trovare una complessità per quell'esercizio..
solo non riesco a trovare una complessità per quell'esercizio..
No mi sa che sopra ho scritto un mucchio di cavolate..
nessuno?..
Ciao,
$k$ e $T$ ipotizziamo siano rappresentati in binario con $d$ bit.
Per il momento riscriviamo il calcolo come:
$sqrt(k^k) (mod T) = k^(k/2) mod T =^{{v = k/2}} k^v mod T$
scomponiamo $v$ come somma di potenze di $2$, $v = 2^{i_1} + .... + 2^{i_u}$ dove $i_1 < .... < i_u$. Calcoliamo le potenze $k^{2^j} mod T$ per $j=1,...,i_u$ dove ognuna è ricavata facendo il quadrato della precedente.
Si ottiene $k^v mod T$ effettuando il prodotto $mod T$ tra le potenze:
$k^{2^{i_1}} mod T * ... * k^{2^{i_u}} mod T$. Il numero di moltiplicazioni è $O(log_2(v))$
Ma ristotituendo $log_2(v) = log_2(k/2) = log_2(k)$. Perciò $O(log_2(k))$ e sapendo che $T <= k^3$ si comprende che comunque rimane di tempo logaritmico.
Per le operazioni si sà che $O(log_2(k)) = O(d)$ quindi lineare nella dimensione del problema. Ma per contarle, basta vedere quante sono le operazioni tra bit per ciascuna moltiplicazione, cioè $O(d^2)$, in totale $O(d^3)$.
Salvo errori, per il valore preciso devi sostituire all'indietro tra le complessità.
"Maryse":
Come faccio a determinare una stima per il numero di operazioni bit necessarie per calcolare $ [√(k^k) (mod T)] $ con T $ <= k^3 $ ?
$k$ e $T$ ipotizziamo siano rappresentati in binario con $d$ bit.
Per il momento riscriviamo il calcolo come:
$sqrt(k^k) (mod T) = k^(k/2) mod T =^{{v = k/2}} k^v mod T$
scomponiamo $v$ come somma di potenze di $2$, $v = 2^{i_1} + .... + 2^{i_u}$ dove $i_1 < .... < i_u$. Calcoliamo le potenze $k^{2^j} mod T$ per $j=1,...,i_u$ dove ognuna è ricavata facendo il quadrato della precedente.
Si ottiene $k^v mod T$ effettuando il prodotto $mod T$ tra le potenze:
$k^{2^{i_1}} mod T * ... * k^{2^{i_u}} mod T$. Il numero di moltiplicazioni è $O(log_2(v))$
Ma ristotituendo $log_2(v) = log_2(k/2) = log_2(k)$. Perciò $O(log_2(k))$ e sapendo che $T <= k^3$ si comprende che comunque rimane di tempo logaritmico.
Per le operazioni si sà che $O(log_2(k)) = O(d)$ quindi lineare nella dimensione del problema. Ma per contarle, basta vedere quante sono le operazioni tra bit per ciascuna moltiplicazione, cioè $O(d^2)$, in totale $O(d^3)$.
Salvo errori, per il valore preciso devi sostituire all'indietro tra le complessità.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo