Złożoność algorytmów

Question

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ź?

Comments

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

Answer 1

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)