Problema python - determinare Big O, respectiv run-time complexity

#1
un_trecator_

Posted 07 December 2020 - 22:29

Junior Member

Grup: Junior Members
Posts: 72
Înscris: 22.04.2020

Salutare,

Am dat peste urmatoarea problema, unde se cere:
What is the run-time complexity of the following algorithm, in terms of n and m?

Ar putea sa-mi spuna cineva care este rezolvarea? Iar daca ar mai gasi timpul sa-mi poate explica cum s-a ajuns la rezolvare, m-as bucura tare mult.

Multumesc!

P.S: Nu exista parti lipsa din cod, asa a venit.

def print_all_codes(n, m):

    def print_01_codes(current, num_digits):

        if num_digits == 0:

            print(current)

        else:

            print_01_codes('0' + current, num_digits - 1)

            print_01_codes('1' + current, num_digits - 1)

    upper_bound = 0

    while True:

        for i in range(upper_bound):

            print_01_codes('', n)

        if upper_bound > m:

            break

        upper_bound += 1

Back to top

#2
halflife

Posted 08 December 2020 - 12:52

Member

Grup: Members
Posts: 761
Înscris: 31.05.2015

~~Deci nu s programator de succes ca alti de pe forum.~~
Cred ca este (m!+1)*2^n pentru ca daca executi functia mare cu diferite numere ca parametri obti toate numerele binare pe n biti de (m!+1) ori.
~~Intreaba pe cei de succes ce este 2^n sau m! daca nu sti ca ei stiu.~~

Edited by MarianG, 08 December 2020 - 13:13.
fara lamentari; post sanctionat

Back to top

#3
dani.user

Posted 08 December 2020 - 13:30

Guru Member

Grup: Senior Members
Posts: 30,238
Înscris: 24.02.2007

Vezi fiecare linie de cate ori se executa. Incepe cu partea de jos, apoi treci la print_all_codes.

a.png 1.94K 8 downloads

Back to top

#4
un_trecator_

Posted 08 December 2020 - 19:27

Junior Member

Grup: Junior Members
Posts: 72
Înscris: 22.04.2020

Va multumesc amandurora!
Voi incerca sa ma ghidez dupa rezultatele voastre pentru a-mi explica cum se determina de fapt run-time complexity.

Doar o ultima intrebare, aveti idee daca un angajator se astepta de la un programator incepator sa stie despre Big O, cand programatorul va urma sa aiba de-a face cu algoritmi zi de zi?

Back to top

#5
dani.user

Posted 08 December 2020 - 22:02

Guru Member

Grup: Senior Members
Posts: 30,238
Înscris: 24.02.2007

Foarte putini urmeaza sa aibe de-a face cu algoritmi zi de zi.

Destui angajatori vor sa stii Big O

Back to top

#6
un_trecator_

Posted 08 December 2020 - 22:39

Junior Member

Grup: Junior Members
Posts: 72
Înscris: 22.04.2020

@dani.user

Iti multumesc pentru raspuns!

O seara faina!

Back to top

#7
halflife

Posted 09 December 2020 - 13:55

Member

Grup: Members
Posts: 761
Înscris: 31.05.2015

dani.user, on 08 decembrie 2020 - 13:30, said:

Vezi fiecare linie de cate ori se executa. Incepe cu partea de jos, apoi treci la print_all_codes.

Attachment

a.png

Dupa mai multe teste cred ca este (m+1)!*2^n. De ce m^2*2^n ?

Back to top

#8
halflife

Posted 12 December 2020 - 17:57

Member

Grup: Members
Posts: 761
Înscris: 31.05.2015

halflife, on 09 decembrie 2020 - 13:55, said:

Dupa mai multe teste cred ca este (m+1)!*2^n. De ce m^2*2^n ?

Imi explica cineva sau sunt prea prost ?

Back to top

Anunturi

Second Opinion

Folosind serviciul second opinion ne puteți trimite RMN-uri, CT -uri, angiografii, fișiere .pdf, documente medicale.

Astfel vă vom putea da o opinie neurochirurgicală, fără ca aceasta să poată înlocui un consult de specialitate. Răspunsurile vor fi date prin e-mail în cel mai scurt timp posibil (de obicei în mai putin de 24 de ore, dar nu mai mult de 48 de ore). Second opinion – Neurohope este un serviciu gratuit.

www.neurohope.ro

Problema python - determinare Big O, respectiv run-time complexity

#1 un_trecator_ Posted 07 December 2020 - 22:29

#2 halflife Posted 08 December 2020 - 12:52

#3 dani.user Posted 08 December 2020 - 13:30

#4 un_trecator_ Posted 08 December 2020 - 19:27

#5 dani.user Posted 08 December 2020 - 22:02

#6 un_trecator_ Posted 08 December 2020 - 22:39

#7 halflife Posted 09 December 2020 - 13:55

#8 halflife Posted 12 December 2020 - 17:57

Anunturi

▶ 0 user(s) are reading this topic

Sign In

#1
un_trecator_

Posted 07 December 2020 - 22:29

#2
halflife

Posted 08 December 2020 - 12:52

#3
dani.user

Posted 08 December 2020 - 13:30

#4
un_trecator_

Posted 08 December 2020 - 19:27

#5
dani.user

Posted 08 December 2020 - 22:02

#6
un_trecator_

Posted 08 December 2020 - 22:39

#7
halflife

Posted 09 December 2020 - 13:55

#8
halflife

Posted 12 December 2020 - 17:57