• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytm o złożoności obliczeniowej czasowej O(n*n)

VPS Starter Arubacloud
0 głosów
327 wizyt
pytanie zadane 21 czerwca 2017 w Algorytmy przez wojtek30 Nowicjusz (120 p.)
Witam, potrzebuje trzech przykładów algorytmów, które mają poszczególne złożoności obliczeniowe czasowe: Algorytm o złożoności obliczeniowej czasowej rzędu O(1). Algorytm o złożoności obliczeniowej czasowej rzędu O(n). Algorytm o złożoności obliczeniowej czasowej rzędu O(n*n). Do każdego algorytmu należy dodać opis analizy jego złożoności. Liczę na Waszą pomoc bo nie wiem jak się do tego w ogóle zabrać  :)

2 odpowiedzi

+1 głos
odpowiedź 21 czerwca 2017 przez Jedras Maniak (54,860 p.)
O(1) => możemy obliczyć sumę wyrazów n-elementowego ciągu arytmetycznego jeśli skorzystamy ze znanego wzoru S = (a1+an)/2*n. Widać tu, że niezależnie od ilości wyrazów w ciągu (n) wykonamy tylko jedną operację (złożoność stała).

O(n) => możemy wykorzystać ten sam przykład co wyżej tylko, że realizujemy go za pomocą pętli, która przechodzi po wszystkich elementach. Widać, że zrobi to tyle razy, ile jest elementów ciągu (n), więc złożoność będzie liniowa.

O(n*n) => sortowanie bąbelkowe
komentarz 21 czerwca 2017 przez wojtek30 Nowicjusz (120 p.)

a jak mam np. taki algorytm

 http://prntscr.com/fmi6jr

to jako parametr charakterystyczny biorę sume ? i jak to zapisać wtedy złożoność czasową ?

coś takiego czy źle to rozumie ?

suma=8 jest parametrem charakterystycznym

O(1)=1+1+1+1=4

O(1) jest dokładnie rzędu stałego 

??

+1 głos
odpowiedź 21 czerwca 2017 przez X3h Dyskutant (9,540 p.)
O(1) wykonanie jakiegokolwiek wzoru.

O(n) np. liniowe przeszukiwanie całej tablicy.

O(n*n) np. Bubble sort.
komentarz 21 czerwca 2017 przez wojtek30 Nowicjusz (120 p.)
A opis analizy złożoności jakoś jesteś w stanie mi objaśnić dla sortowania właśnie ?
komentarz 22 czerwca 2017 przez X3h Dyskutant (9,540 p.)
Przy wyszukiwaniu liniowym mając n elementów w tablicy ograniczasz z góry przez O(n) ponieważ wykonujesz pętlę tylko raz. W Bubble sort wykonujesz pętlę w pętli. Dla każdego elementu tablicy porównujesz każdy element tej samej tablicy

Podobne pytania

0 głosów
0 odpowiedzi 235 wizyt
0 głosów
0 odpowiedzi 674 wizyt
0 głosów
2 odpowiedzi 490 wizyt
pytanie zadane 19 lipca 2015 w Algorytmy przez demo094 Użytkownik (630 p.)

92,455 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...