}
==

h2. Algoritmi mai serioşi
Deşi ceea ce am prezentat mai sus sunt mai degrabă trucuri de implementare decât algoritmi serioşi şi în general nu se acordă aşa mare importanţă detaliilor de genul acesta, câteodată asemenea trucuri se pot dovedi importante mai ales în timpul concursurilor.
Un exemplu ar fi problema rundei 12 de la concursul de programare Bursele Agora. Acolo se cerea găsirea numărului de dreptunghiuri conţinute de o matrice binară $a$ care au în colţuri 1. Un algoritm de complexitate $O(n^2^ · m)$ ar fi fost următorul: se consideră fiecare pereche formată din două linii şi se numãrã câte perechi ( $a{~i,k~}$, $a{~j,k~}$ ) pentru care $a{~i,k~}$ = 1 şi $a{~j,k~}$ = 1 există. Fie acest număr $x$. Atunci numărul de dreptunghiuri care au colţurile pe aceste două linii va fi $x · (x - 1)$ / 2.
Un asemenea algoritm ar fi luat numai 64 de puncte deoarece restricţiile date erau mari ( $n ≤ 200$ , $m ≤ 2500$ ). Putem rescrie condiţia  a[i][k] $= =$ 1 && a[j][k] $= =$ 1 ca şi ( a[i][k] ^ a[j][k] $= =$ 1 ), deci putem modifica rezolvarea anterioară în modul următor:
==code(cpp)|
pentru fiecare i
  pentru fiecare j > i
    b = a[i] ^ a[j];
  sfârşit pentru
sfârşit pentru
  numaraBitiUnu(b)
==
 
Dacă în loc să păstrăm în $a[i][j]$ un element al matricei binare, păstram 16 elemente, atunci în linia $b$ = $a[i] ^ a[j]$ se efectuează cel mult $2500 / 16$ calcule în loc de $2500$ de calcule. Acum ce a rămas de optimizat este metoda numaraBitiUnu. Dacă folosim preprocesarea, atunci această metodă va fi compusă şi ea $2500/16$ calcule. Se observă că în acest fel am mărit viteza de execuţie a algoritmului cu un factor de $16$.
 
Alt exemplu ar fi problema rundei 17. În acea problemă se cere determinarea numărului de sume distincte care se pot obţine folosind nişte obiecte cu valori date folosind fiecare obiect pentru o sumă cel mult o dată. Din nou o rezolvare directă, folosind marcarea pe un şir de valori logice n-ar fi obţinut punctaj maxim. Pentru obţinerea punctajului maxim următoarea idee ar fi putut fi folosită cu succes: şirul de valori logice se condensează într-un sir de întregi reprezentaţi pe $16$ biţi, şi acum actualizarea se face asupra a 16 valori deodată. Deci şi aici se câştiga un factor de viteză egal cu 8 (datorită detaliilor de implementare).
 
Un al treilea exemplu ar fi problema Viteza de la a 9-a rundă a concursului organizat de *.campion* anul acesta. Acolo se cerea determinarea celui mai mare divizor comun a două numere binare de cel mult 10000 de cifre. După cum se ştie, complexitatea algoritmului de determinare a celui mai mare divizor comun a două numere este logaritmică, acest fapt este adevărat atunci când operaţiile efectuate sunt constante, dar în rezolvarea noastră apar numere mari, deci o estimare a numărului de calcule ar fi $maxn$ · $maxn$ · $log maxn$ (împărţirea are în medie costul $maxn$ · $maxn$ dacă nu implementăm metode mai laborioase). Acest număr este prea mare pentru timpul de rezolvare care ne este cerut. Pentru a evita împărţirea, care este operaţia cea mai costisitoare, putem folosi algoritmul de determinare a celui mai mare divizor comun binar care se foloseşte de următoarele proprietăţi:
$cmmdc(a, b)$ = 2 * $cmmdc(a / 2, b / 2)$, dacă $a$ si $b$ sunt numere pare;
$cmmdc(a, b)$ = $cmmdc(a, b / 2)$, dacã $a$ este impar;
$cmmdc(a, b)$ = $cmmdc(a - b, b)$, dacã $a$ este impar, $b$ este impar şi $a$ > $b$.
 
Aplicând acest algoritm numărul de calcule s-a redus la $maxn$ · $log maxn$, dar nici acest număr nu este suficient de mic, şi deci
pentru accelerarea algoritmului folosim ideea utilizată în cele două probleme de mai sus. Împachetăm numărul în întregi, în pachete de câte 30 de biţi, şi atunci deplasarea la stânga (adică împărţirea la 2) şi scăderea vor fi de 30 de ori mai rapide.
 
Să încercăm acum rezolvarea unei probleme în care eficienţa este cea mai importantă, mai importantă decât lizibilitatea codului obţinut. Problema are următorul enunţ:
 
bq. Se consideră un număr $n$. Să se determine numerele prime mai mici sau egale cu $n$, unde $n$ ≤ 10.000.000.
Practic această problemă ne va fi utilă în testarea rapidă a primalităţii numerelor mai mici sau egale cu $n$.
Putem încerca mai multe rezolvări, dar în practică cea mai rapidă se dovedeste de obicei cea numită ciurul lui Eratostene. Implementarea banală a algoritmului ar fi urmãtoarea:
==code(cpp)|
define maxsize 10000000
 
char at[maxsize]; //vector de valori logice în care numerele prime vor fi marcate cu 0
 
int n;
int isPrime(int x){
return (!at[x]) ;
}
 
void sieve(){
  int i, j;
  memset(at,0,sizeof(at)) ;
  for (i = 2; i <= maxsize; i++)
     if (!at[i])
       for (j = i + i; j <= maxsize; j += i)
          at[j]=1; //marcãm toþi multipli lui i ca fiind numere prime
}
==