Keskustelu: Yleinen keskustelu: Algoritmin Big O

Jos on funktio joka saa ainoana parametrinään (positiivisen ja mielivaltaisen suuren) kokonaisluvun n, ja palauttaa jonkin tietorakenteen muodossa luvun e n-desimaalisen likiarvon, niin mikä sen Big O luokitus olisi?

Pseudoa:

float calc_e(int n) {
float sum = 1.0, tmp = 1.0;
int kiek = 1;
do {
   tmp /= kiek;
   kiek++;
   sum += tmp;
} while (tmp > 10^(-n));
return sum;
}

Oletetaan siis, että float voisi pitää mielivaltaisen monta desimaalia. Eikös tuossa oikdeiden desimaalien lukumäärä kasva yli expotentiaalisesti?

n! > a^n, kun n on tarpeeksi suuri

Mikäli jakolasku on O(n^2*log(n)), se antaisi algoritmille luokituksen O((n*log(n))^2).

Menikö oikein?

Algoritmissa toistetaan silmukkaa, jossa suoritetaan jakolasku ja nopeita yhteenlaskuja. Jos yksittäinen jakolasku vie ajan t1 ja ajassa t2 tmp pienenee alle 10^(-n), on aikavaativuus O(t1*t2).

Tarkkuutta. Kaavassa n!>a^n et ole määritellyt, mikä on a. Algoritmien vaativuuksia voidaan luokitella monin tavoin, esim. aikavaativuuden ja muistinkäytönvaativuuden mukaan.

Kurssilla oletetaan, että kertolasku ja yhteenlasku vie yhtä paljon aikaa. Ero on enintään jotain vakiokertaluokkaa, jolloin iso O hävittää ne kertoimet pois. Lisäksi keskitymme lähinnä aikavaativuuteen, koska se on ilmeisesti helpompi asia (aikaa on "loputtomasti", mutta RAMia voi joutua swappaamaan kovalevylle jne.)

lainaus:

n!>a^n et ole määritellyt, mikä on a

a saa olla mikä tahansa (positiivinen) reaaliluku. Halusin vain osoittaa että n! kasvaa nopeammin kuin expotentiaalisesti, jolloin silmukan toistoja tarvitaan enintään luokkaa O(log(n)).

msdos464 kirjoitti:

Halusin vain osoittaa että n! kasvaa nopeammin kuin expotentiaalisesti, jolloin silmukan toistoja tarvitaan enintään luokkaa O(log(n)).

Ahaa. Tämä seuraa Stirlingin kaavasta. Kun n>3e,
sqrt(2 pii n)*(n/e)^n>sqrt(6 pii e)*3^n>3^n>e^n.