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

Złożoność algorytmów

Fiszki IT
Fiszki IT
0 głosów
63 wizyt
pytanie zadane 14 czerwca w Algorytmy przez Tanormalnie Użytkownik (550 p.)
Ile razy przeciętnie algorytm sortowania przez wybieranie jest szybszy niż algorytm sortowania bąbelkowego dla zbioru złożonego z 256 elementów?

Policzyłem to zadanie i wyszło mi 2. Czy to poprawna odpowiedź?
komentarz 14 czerwca przez tkz Nałogowiec (39,540 p.)
Pokaż obliczenia. Oba algorytmy mają taką samą klasę złożoności czasowej.

1 odpowiedź

0 głosów
odpowiedź 14 czerwca przez Wiciorny Mędrzec (166,950 p.)
wybrane 16 czerwca przez Tanormalnie
 
Najlepsza

Pytanie czy faktycznie tu chodzi o szybkość ? Złożoność czasowa - jak @tkz napisał to właśnie szybkość, natomiast mnogość wykonania operacji to złożoność obliczeniowa - >  ilość zasobów komputerowych potrzebnych do jego wykonania: 

Złożoność czasowa jest taka sama dla obu algorytmów, tzn jej rząd bo jest to O(n^2).
Natomiast złożoności obliczeniowe można porównać - gdyż bąbelkowe może zapewnić złożoność O(1) względem wybierania O(n^2).

Tutaj masz porównanie dwóch algorytmów i dlaczego Bubble jest wolniejszy :  W SYTUACJI większych problemów i wzrastającej liczby danych 
https://www.geeksforgeeks.org/comparison-among-bubble-sort-selection-sort-and-insertion-sort/

 

Podejrzewam że u Ciebie wystarczy porównanie   0(n) - > dla optymistycznego vs O(n^2). Dla 256 elementów sortowanie przez wybieranie ma O(256) - natomiast dla bubble sort O(256^2) 
 

Podobne pytania

0 głosów
2 odpowiedzi 155 wizyt
pytanie zadane 5 grudnia 2019 w Algorytmy przez progNewbie Obywatel (1,130 p.)
0 głosów
1 odpowiedź 91 wizyt
pytanie zadane 1 listopada 2020 w Algorytmy przez wixy0 Gaduła (3,700 p.)
0 głosów
1 odpowiedź 100 wizyt
pytanie zadane 25 kwietnia 2020 w C i C++ przez Tacoo Nowicjusz (150 p.)
Porady nie od parady
Wynikowy wygląd pytania, odpowiedzi czy komentarza, różni się od tego zaprezentowanego w edytorze postów. Stosuj więc funkcję Podgląd posta znajdującą się pod edytorem, aby upewnić się, czy na pewno ostateczny rezultat ci odpowiada.Podgląd posta

84,745 zapytań

133,549 odpowiedzi

295,964 komentarzy

56,007 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...