Python - rychlosti funkcii v zoznamoch

sliziky

Zdravim,chcem sa spytat,majme 2 zoznamy ,jeden prazdny a druhy naplneny cislami,povedzme ze chceme spravit

prazdny+=druhyZoznam

,bude v tomto pripade casova zlozitost O(n) kde n je dlzka druhehoZoznamu ?
A este jedno,nasiel som ze .remove() ma casovu zlozitost O(n),povedzme ze mame nasledujuci kod

Kód: Vybrať všetko

for i in zoznam:
    if i==4:
        zoznam.remove(i)

,tak aka bude tato zlozitost? Kedze for je O(n) ,aj remove je O(n) a nie som si isty ,ci to bude O(n^2) alebo O(2n) ,dakujem pekne!

Redpoint1

Ahoj,

Kód: Vybrať všetko

prazdny+=druhyZoznam

Podľa https://wiki.python.org/moin/TimeComplexity je to ako si pisal, teda O(k)

Kód: Vybrať všetko

for i in zoznam:
    if i==4:
        zoznam.remove(i)

Kedze prechadzas cez cely zoznam, tak je to O(n^2) (i ked kvoli tej podmienke nie som si uplne isty)

skjerp-deg

Redpoint1 napísal:
Kód: Vybrať všetko
for i in zoznam: // n
    if i==4: // 1
        zoznam.remove(i) // n
Kedze prechadzas cez cely zoznam, tak je to O(n^2) (i ked kvoli tej podmienke nie som si uplne isty)

Prvé áno, keďže += pri listoch je vlastne extend(), teda je to O(n)

Druhé - remove sa vykoná iba raz, takže by to malo byť O(n + n) = O(2n) = O(n), nie?

Redpoint1

skjerp-deg napísal: Druhé - remove sa vykoná iba raz, takže by to malo byť O(n + n) = O(2n) = O(n), nie?

Kedze v zozname je mozno mat hodnotu viac ako raz, tak worst case je O(n^2), len neviem ci je to zaroven aj priemerny.

skjerp-deg

Jasné, moja chyba. Worst case je teda naozaj O(n^2).

sliziky

Sorry chlapci,mám tam jednu zásadnú chybu,čo v tomto prípade? To už bude asi O(n)

Kód: Vybrať všetko

for i in zoznam: // n
    if i==4: // 1
        zoznam.remove(i) // n
        break

harrison314

ano ak robi ten breal to co si myslim, tak je to O(n)

skjerp-deg

jj, v tom prípade platí, čo som písal vyššie, teda O(n)

Ináč, predpokladám že ti je to jasné, ale keby náhodou nie - tá iterácia cez list je tam nepotrebná, pretože vnútri remove() sa robí práve to.

Kód: Vybrať všetko

zoznam.remove(4)
#resp:
try:
    zoznam.remove(4)
except ValueError as e:
    print('4 not in the list')

je všetko čo potrebuješ.

sliziky

To jasne ze chapem,toto je iba taky priklad,v mojom pripade potrebujem loopovat polom ,dakujem

Python - rychlosti funkcii v zoznamoch

Python - rychlosti funkcii v zoznamoch

Re: Python - rychlosti funkcii v zoznamoch

Re: Python - rychlosti funkcii v zoznamoch

Re: Python - rychlosti funkcii v zoznamoch

Re: Python - rychlosti funkcii v zoznamoch

Re: Python - rychlosti funkcii v zoznamoch

Re: Python - rychlosti funkcii v zoznamoch

Re: Python - rychlosti funkcii v zoznamoch

Re: Python - rychlosti funkcii v zoznamoch