3:56 cred ca se considera pentru cel mai rau caz ( worst case scenario) si pe langa comparatie, mai este si atribuire. Multumesc pentru explicatiile clare.
Daca imi puteti raspunde la toate aceste intrebari in decurs de o saptamana, eu sunt foarte multumit! Un videoclip super interesant, are mare legatura cu algebra din treapta I de liceu care mie imi place! O saptamana faina sa aveti si mai asteptam clipuri de la dvs. :))
Cumva pentru ca n reprezinta cel mai mare numar de operatii efectuate intr-o singura structura de date (de exemplu for-ul, care are trei instructiuni)?
Un polinom e format din monoame, cel de grad maxim este cel mai important. Ca să dau un exemplu din viața reală, dacă ai avea în cont n^2 + 3n euro în cont unde n=10.000, înseamnă că ai peste 100.000.000 euro. De fapt ce este peste o sută de milioane e mărunțiș. Așa este și aici. Numărul mare de operații este dat de n^2, nu de 3n. Ți-aș sugera să studiezi mai mult despre complexitatea algoritmilor de pe net sau de la profesorul tău.
De ce daca vrem sa generam permutarile, respectiv submultimile unei multimi cu n elemente, trebuie efectuat un numar MINIM de x, respectiv y operatii, si nu un numar FIX de x, respectiv y operatii (ce ne impiedica)?...
Si, de asemenea, cum ati stabilit (tinandu-se cont de monomuri de grad maxim sau ce ati spus mai devreme) ca (scuzati cacofonia) complexitatea polinomiala are expresia n^k, si complexitatea exponentiala are expresia k^n?
De ce ati considerat algoritmul de complexitate O(logn), adica O de logaritm zecimal din n (caci asa se scrie, logn sau lgn), cand baza lui era 2? Da, nu este un algoritm eficient deoarece cautam divizorul maxim impar (mai eficient ar fi fost sa cautam divizorul maxim par, stiind ca n are un singur divizor impar mai mare decat 1), dar, totusi, 2 nu este cea mai mica baza naturala (caci vorbim de divizori) a unui logaritm, este 1 (nu poate fi 0, caci 0 la orice putere face 0, iar numarul de operatii efectuate in while-ul de pe tabla este mai mare decat 0, pentru ca si daca am fi aflat divizorul maxim par si n ar fi avut un singur divizor impar mai mare decat 1, divizorul impar il divide pe n cel putin o data - caci, n fiind numar par, el este mai mic decat n -), adica ar fi putut exista si un algoritm mai ineficient!... Asa ca, eu consider ca trebuia scrisa si baza 2 in exprimarea complexitatii!
Cum adica un numar constant de operatii indiferent de numarul de valori citite? Pai daca x si y sunt tablouri, mai sunt doar doua operatii de citire?...
La primul exercitiu de determinare a complexitatii unui algoritm, cum ati ajuns la concluzia ca 2 la puterea k este egal cu n, unde k este numarul de pasi efectuati de primul for pana atunci (concomitent, de toate cele trei instructiuni ale sale)?...
Ati spus ca: "Diferenta celor doua siruri e un numar mai mic decat 1." Ce inseamna "diferenta dintre doua siruri" si care este al doilea sir? Si cred ca ati vrut sa spuneti "diferenta dintre o suma si un sir, sirul cu termenul general logaritm zecimal din n, unde n e un numar natural nenul"!...
Imi puteti trimite link-ul la adresa caruia gasesc demonstratia riguroasa a faptului ca n factorial mai mare sau egal decat 2 la puterea n, pentru orice n mai mare sau egal decat 4?...
Un al doilea lucru: La calcularea sumei: 1 + (1 / 2) + (1 / 3) + ... + (1 / n) de ce ati spus ca aceasta tinde catre logn? Din nou, tot logaritm zecimal din n? Dar eu stiam ca aceasta suma (pentru n suficient de mare) tinde catre valoarea constantei pi!...
1 + (1 / 2) + (1 / 3) + ... + (1 / n) este un șir cu limita infinit, la fel și log(n) tinde la infinit, indiferent de bază>=2. Dar șirul 1 + (1 / 2) + (1 / 3) + ... + (1 / n) - ln(n) (ln(n) este logaritmul natural, deci in baza e) are limita intre 0 și 1. Deci dacă se fac 1 + (1 / 2) + (1 / 3) + ... + (1 / n) operații, practic se fac log n operații. Baza logaritmului nu contează, de obicei e baza 2.
Pai o data spuneti: "Ambele probleme au o complexitate exponentiala, prima, O de n factorial, a doua, O de 2 la n, asa cum am explicat, nu se poate o complexitate mai buna.", si alta data spuneti: "Evident, vrem ca toti algoritmii pe care-i rezolvam sa aiba complexitate cat mai mica, nu exponentiala, dar uneori se pare ca nu avem de ales..." Eu nu prea inteleg... Si ce inseamna "a rezolva un algoritm"?
La Ciurul lui Eratostene, ati spus ca: "Vrem sa determinam in vectorul d[], pentru fiecare numar intre 1 si n, cati divizori are i. Un ciur clasic in care, pentru fiecare numar intre 1 si n, i este divizor pentru fiecare multiplu al sau, adica primul multiplu este chiar el insusi, i, urmatorul, observati, crestem din i in i, urmatorul este 2i, 3i, si asa mai departe. La fiecare pas in vectorul d[], memoram la pozitia j cati divizori are j." O prima intrebare ar fi: "Ce legatura are acest algoritm cu determinarea tuturor numerelor prime mai mici sau egale cu o valoare data, n?" Mi-ar placea sa imi dau seama, insa la ce ati scris dvs. pe tabla nu ati adaugat si operatorul de insertie in stream (
Vreau sa compar aceasta complexitate (monomul de grad maxim al polinomului egal cu numarul de operatii) cu cea a functiei strtok(). De asta va cer sa mi-o calculati.
Care este complexitatea urmatorului algoritm (rupe o fraza in cuvinte fara sa foloseasca strtok() si eu l-am inventat)? #include #include using namespace std; char propozitie[200005]; int nrCuvinte = 0; char cuvinte[200005][50]; int dimensiuneCuvinte[50]; char separatori[] = " ,.;!?-"; bool eSeparator(char c) { for (int i = 0; i < strlen(separatori); i++) if (c == separatori[i]) return true; return false; } int main() { cin.get(propozitie, 200004); char caracterulAnterior = '.'; for (int i = 0; i < strlen(propozitie); i++) { if (!eSeparator(propozitie[i])) { if (eSeparator(caracterulAnterior)) nrCuvinte++; dimensiuneCuvinte[nrCuvinte]++; cuvinte[nrCuvinte][dimensiuneCuvinte[nrCuvinte]] = propozitie[i]; } caracterulAnterior = propozitie[i]; } for (int i = 1; i
Complexitatea este O(n), unde n este lungimea șirului inițial Doar că olosești strlen() inadecvat. Trebuie să calculezi de la început într-o variabilă, de genul L = strlen(propozitie), apoi scrii for (i = 0; i < L; i++), altfel se calculeaz[ la fiecare itera'ia lungimea ;i d[ peste cap complexitatea.
3:56 cred ca se considera pentru cel mai rau caz ( worst case scenario) si pe langa comparatie, mai este si atribuire.
Multumesc pentru explicatiile clare.
Daca imi puteti raspunde la toate aceste intrebari in decurs de o saptamana, eu sunt foarte multumit! Un videoclip super interesant, are mare legatura cu algebra din treapta I de liceu care mie imi place! O saptamana faina sa aveti si mai asteptam clipuri de la dvs. :))
Cumva pentru ca n reprezinta cel mai mare numar de operatii efectuate intr-o singura structura de date (de exemplu for-ul, care are trei instructiuni)?
De unde vine acel O din fata expresiei complexitatii (este chiar o abreviere pentru complexitate)?
I se spune BIG O în engleză, e de fapt litera grecească teta
Si de ce ne intereseaza doar acel monom de grad maxim? Ce inseamna ca ne intereseaza?
Un polinom e format din monoame, cel de grad maxim este cel mai important. Ca să dau un exemplu din viața reală, dacă ai avea în cont n^2 + 3n euro în cont unde n=10.000, înseamnă că ai peste 100.000.000 euro. De fapt ce este peste o sută de milioane e mărunțiș. Așa este și aici. Numărul mare de operații este dat de n^2, nu de 3n. Ți-aș sugera să studiezi mai mult despre complexitatea algoritmilor de pe net sau de la profesorul tău.
Gata domnu v-am facut promovare
Ultima instructiune indicata de o structura de date?
De ce daca vrem sa generam permutarile, respectiv submultimile unei multimi cu n elemente, trebuie efectuat un numar MINIM de x, respectiv y operatii, si nu un numar FIX de x, respectiv y operatii (ce ne impiedica)?...
Si, de asemenea, cum ati stabilit (tinandu-se cont de monomuri de grad maxim sau ce ati spus mai devreme) ca (scuzati cacofonia) complexitatea polinomiala are expresia n^k, si complexitatea exponentiala are expresia k^n?
De ce ati considerat algoritmul de complexitate O(logn), adica O de logaritm zecimal din n (caci asa se scrie, logn sau lgn), cand baza lui era 2? Da, nu este un algoritm eficient deoarece cautam divizorul maxim impar (mai eficient ar fi fost sa cautam divizorul maxim par, stiind ca n are un singur divizor impar mai mare decat 1), dar, totusi, 2 nu este cea mai mica baza naturala (caci vorbim de divizori) a unui logaritm, este 1 (nu poate fi 0, caci 0 la orice putere face 0, iar numarul de operatii efectuate in while-ul de pe tabla este mai mare decat 0, pentru ca si daca am fi aflat divizorul maxim par si n ar fi avut un singur divizor impar mai mare decat 1, divizorul impar il divide pe n cel putin o data - caci, n fiind numar par, el este mai mic decat n -), adica ar fi putut exista si un algoritm mai ineficient!... Asa ca, eu consider ca trebuia scrisa si baza 2 in exprimarea complexitatii!
Cum adica un numar constant de operatii indiferent de numarul de valori citite? Pai daca x si y sunt tablouri, mai sunt doar doua operatii de citire?...
Adica stiu ca este "o constanta", dar ce valoare are ea pentru exemplele de calculul complexitatii algoritmilor date?...
La primul exercitiu de determinare a complexitatii unui algoritm, cum ati ajuns la concluzia ca 2 la puterea k este egal cu n, unde k este numarul de pasi efectuati de primul for pana atunci (concomitent, de toate cele trei instructiuni ale sale)?...
abureala
De fapt, as pune altfel intrebarea: Cum ati stabilit formula i = n / (2 ^ k)?
De ce una se numeste "polinomiala" si alta "exponentiala"?
Ati spus ca: "Diferenta celor doua siruri e un numar mai mic decat 1." Ce inseamna "diferenta dintre doua siruri" si care este al doilea sir? Si cred ca ati vrut sa spuneti "diferenta dintre o suma si un sir, sirul cu termenul general logaritm zecimal din n, unde n e un numar natural nenul"!...
Imi puteti trimite link-ul la adresa caruia gasesc demonstratia riguroasa a faptului ca n factorial mai mare sau egal decat 2 la puterea n, pentru orice n mai mare sau egal decat 4?...
se demonstreaza prin inductie matematica
Un al doilea lucru: La calcularea sumei: 1 + (1 / 2) + (1 / 3) + ... + (1 / n) de ce ati spus ca aceasta tinde catre logn? Din nou, tot logaritm zecimal din n? Dar eu stiam ca aceasta suma (pentru n suficient de mare) tinde catre valoarea constantei pi!...
1 + (1 / 2) + (1 / 3) + ... + (1 / n) este un șir cu limita infinit, la fel și log(n) tinde la infinit, indiferent de bază>=2. Dar șirul 1 + (1 / 2) + (1 / 3) + ... + (1 / n) - ln(n) (ln(n) este logaritmul natural, deci in baza e) are limita intre 0 și 1. Deci dacă se fac 1 + (1 / 2) + (1 / 3) + ... + (1 / n) operații, practic se fac log n operații. Baza logaritmului nu contează, de obicei e baza 2.
Ce inseamna monomul de grad maxim?
Eu știam că în calcularea complexității algoritmilor nu se iau în considerare operațiile de citire și afișare. Este adevărat?
Ba se iau în considerare, e esențial.
@@dpracsiu Am înțeles! Mulțumesc!
Si mai puteti spune o data de ce k este o constanta?
Ce inseamna instructiunea de baza?
Pai o data spuneti: "Ambele probleme au o complexitate exponentiala, prima, O de n factorial, a doua, O de 2 la n, asa cum am explicat, nu se poate o complexitate mai buna.", si alta data spuneti: "Evident, vrem ca toti algoritmii pe care-i rezolvam sa aiba complexitate cat mai mica, nu exponentiala, dar uneori se pare ca nu avem de ales..." Eu nu prea inteleg... Si ce inseamna "a rezolva un algoritm"?
La Ciurul lui Eratostene, ati spus ca: "Vrem sa determinam in vectorul d[], pentru fiecare numar intre 1 si n, cati divizori are i. Un ciur clasic in care, pentru fiecare numar intre 1 si n, i este divizor pentru fiecare multiplu al sau, adica primul multiplu este chiar el insusi, i, urmatorul, observati, crestem din i in i, urmatorul este 2i, 3i, si asa mai departe. La fiecare pas in vectorul d[], memoram la pozitia j cati divizori are j." O prima intrebare ar fi: "Ce legatura are acest algoritm cu determinarea tuturor numerelor prime mai mici sau egale cu o valoare data, n?" Mi-ar placea sa imi dau seama, insa la ce ati scris dvs. pe tabla nu ati adaugat si operatorul de insertie in stream (
Exista sirul logn?
Complexitate log N, adica pasii pana obtii solutia e in cel mai rau caz O( log N). Se considera ca sirul are N elemente
@@dinohunter7176 Mulțumesc că ați avut bunul simț de a-mi răspunde!
Si cine este k?
Vreau sa compar aceasta complexitate (monomul de grad maxim al polinomului egal cu numarul de operatii) cu cea a functiei strtok(). De asta va cer sa mi-o calculati.
V.ar interesa o colaborare în Canada ?
Ce fel de colaborare?
Foarte frumoasa camasa cu matrice
Care este complexitatea urmatorului algoritm (rupe o fraza in cuvinte fara sa foloseasca strtok() si eu l-am inventat)? #include
#include
using namespace std;
char propozitie[200005];
int nrCuvinte = 0;
char cuvinte[200005][50];
int dimensiuneCuvinte[50];
char separatori[] = " ,.;!?-";
bool eSeparator(char c)
{
for (int i = 0; i < strlen(separatori); i++)
if (c == separatori[i])
return true;
return false;
}
int main()
{
cin.get(propozitie, 200004);
char caracterulAnterior = '.';
for (int i = 0; i < strlen(propozitie); i++)
{
if (!eSeparator(propozitie[i]))
{
if (eSeparator(caracterulAnterior))
nrCuvinte++;
dimensiuneCuvinte[nrCuvinte]++;
cuvinte[nrCuvinte][dimensiuneCuvinte[nrCuvinte]] = propozitie[i];
}
caracterulAnterior = propozitie[i];
}
for (int i = 1; i
Complexitatea este O(n), unde n este lungimea șirului inițial
Doar că olosești strlen() inadecvat. Trebuie să calculezi de la început într-o variabilă, de genul L = strlen(propozitie), apoi scrii for (i = 0; i < L; i++), altfel se calculeaz[ la fiecare itera'ia lungimea ;i d[ peste cap complexitatea.
@@dpracsiu Mulțumesc! O să țin cont!