Piccolo problema di algoritimi

[rеpne scasb]

■

[wingman87]

Originariamente inviato da rеpne scasb

q e' il rapporto tra a3 e a2 che per semplificazione l'ho supposto uguale a quello esistente tra a2 e a1. a1 a2 e a3 sono il peso rispetto tempo per n (a3,a2) e m (a1). Per quanto riguarda k e m non comprendo cosa ci sia da spiegare e' come se avessi scritto 18*2=36 e mi stessi chiedendo spiegazioni sul perche' 18 per 2 fa 36.

Infatti quello che non capivo era la prima parte, e a dire la verità ancora adesso non mi sembra corretto. Parlo di porre q=a3/a2 e al contempo anche q=a2/a1, questo si può avere solo con certe triple di a1,a2,a3 e in questo caso non mi sembra verosimile... boh, comunque ne sai certo più tu di me, se mi dici che è così mi fido.

[rеpne scasb]

■

[Furla]

Originariamente inviato da rеpne scasb

a3*n*ln(n)<a1*MAX_NUMBER + a2 * n

e non con quell'obbrobrio che hai scritto tu:

m log(m) >= n

Adesso e' chiaro? Non puoi comparare il peso di n rispetto a MAX_NUMBERS prendendoli come valori assoluti, prescindendo dalle costanti moltiplicativi a1, a2 e a3. Se confronti n e MAX_NUMBERS a meno di a1, a2 e a3 confronti le pere con le banane.

cionci è partito da un'ipotesi quasi sempre verificata, cioè che m<<n (n<<MAX_NUMBER, secondo la tua nomenclatura), perché i valori rappresentabili sono 2^32 (e determinano la dimensione della bitmap), mentre la cardinalità degli array da dare in pasto alle funzioni difficilmente supera qualche migliaio.

in tali e consuete situazioni, sempre secondo la tua nomenclatura:

MAX_NUMBER + a * n = O(MAX_NUMBER)

e la tua disequazione

a3*n*ln(n) < a1*MAX_NUMBER + a2 * n

diventa

O(nlogn) < O(MAX_NUMBER)

che è coerente con quella scritta, in maniera informale, da cionci.

[cionci]

Originariamente inviato da Furla

che è coerente con quella scritta, in maniera informale, da cionci.

Che poi è quello che volevo dire...l'ho anche scritto a parole

[rеpne scasb]

■

[Tommo]

Originariamente inviato da rеpne scasb

    if((bitmap=calloc(1<<((sizeof(long)<<3)-3),1))==NULL)

	k=(x<<1)-j;
	a1=((unsigned)(j+2147483648))>>3;
	b1=((unsigned)(k+2147483648))>>3;
	a2=1<<(j&0x07);
	b2=1<<(k&0x07);

OT ma... volevo chiedere come mai usi sempre shifts anche per le cose più semplici, addirittura per sostituire una costante (512).
Oltre a rendere il codice abbastanza incomprensibile, siamo sicuri che su architetture moderne sia minimamente vantaggioso?
Le moderne unità vettoriali (GPU) manco li supportano, per esempio.

[rеpne scasb]

■

[Tommo]

Ma dici sul serio?

[rеpne scasb]

■

[cdimauro]

Originariamente inviato da Tommo

OT ma... volevo chiedere come mai usi sempre shifts anche per le cose più semplici, addirittura per sostituire una costante (512).
Oltre a rendere il codice abbastanza incomprensibile, siamo sicuri che su architetture moderne sia minimamente vantaggioso?
Le moderne unità vettoriali (GPU) manco li supportano, per esempio.

C'è di peggio: http://en.wikipedia.org/wiki/Interna...C_Code_Contest