Złożoność algorytmów

pytanie zadane 14 czerwca 2021 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 2021 przez tkz Nałogowiec (42,040 p.)

Pokaż obliczenia. Oba algorytmy mają taką samą klasę złożoności czasowej.

1 odpowiedź

odpowiedź 14 czerwca 2021 przez Wiciorny Ekspert (283,260 p.)
wybrane 16 czerwca 2021 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)