Ile czasu jest potrzebne na wykonanie algorytmu

Cześć,
Jestem uczniem technikum i zacząłem się trochę uczyć o złożoności algorytmów.
Trochę nie rozumiem pewnego rozumowania. Załóżmy że mamy algorytm o złożoności n^3 i załóżmy że dla danych n=3 algorytm wykonuje się w 81sekund.
Jak mogę obliczyć ile czasu (przybliżony) zajmie wykonanie tego algorytmu dla danych np n=9 (3x większe)?

Czy odpowiedzią będzie tutaj 243sekund?
Czy ktoś mógłby mnie nakierować, albo może podrzucić jakieś strony które to tłumaczą?

Jeden pomiar nie wystarczy jesli masz staly koszt.
Zmierz 3 rozne rozmiary, najlepiej rosnace wykladniczo: 10, 100 i 1000
Wtedy bedziesz mogl oddzielic koszt staly od zmiennego.

vpiotr napisał(a):

Jeden pomiar nie wystarczy jesli masz staly koszt.
Zmierz 3 rozne rozmiary, najlepiej rosnace wykladniczo: 10, 100 i 1000
Wtedy bedziesz mogl oddzielic koszt staly od zmiennego.

Tak, to na pewno by pomogło, tyle że to zadanie jest bardziej w stronę matematyczną. Zakładając że algorytm w obu przypadkach jest odpalany na tym samym komputerze, z taką samą dokładnością jeśli chodzi o użycie mocy itd. (perfekcyjny przypadek). Pierwszy przypadek n=3 - 81 sekund, drugi przypadek n jest 3x większe - ile sekund? Można to robić na krzyż?
Jak wtedy można takie coś wyliczyć?

No na pewno nie 3 razy dluzej (a duzo dluzej).

Jakbys mial zlozonosc liniowa i dla n = 300 wykonywalby sie w 300 sekund to dla n = 900 wykonywalby sie 3x dluzej, 900 sekund. Jesli masz n^3 to zakladam, ze wspolczynnik tez skalujesz w ten sposob (podnosisz do szescianu)

Skoro masz złożoność n^3 i wiesz, że dla 3 elementów wykonuje się 81 sekund to można wyliczyć,
ile czasu wylicza się pojedynczy "krok programu" = X[s].

( czas wykonywania jednego kroku to całkowity czas podzielony przez ilość kroków wynikających ze złożoności algorytmu )

z powyższego wynika, że pojedynczy krok wykonuje się;



I dalej... Skoro wiemy ile twa "krok programu" to już łatwo wyliczyć, że dla 9 elementów czas będzie wynosił





Jeśli się nie pomyliłem ... Chyba wolałbym to na kartce pisać niż tekstowo :-)

stivens napisał(a):

No na pewno nie 3 razy dluzej (a duzo dluzej).

Jakbys mial zlozonosc liniowa i dla n = 300 wykonywalby sie w 300 sekund to dla n = 900 wykonywalby sie 3x dluzej, 900 sekund. Jesli masz n^3 to zakladam, ze wspolczynnik tez skalujesz w ten sposob (podnosisz do szescianu)

Już rozumiem, czyli w tym przypadku 2187s byłoby poprawną odpowiedzią. Dzięki

Można do tego podejść inaczej. Z zadania można ułożyć równanie:
(A*N)^3=T
A - stała czasowa
N - wielkość danych
T - czas wykonania algorytmu

Dla N=3 i T=81, co wynika z danych, podstawiamy:
(A*3)^3=81
Teraz można obliczyć stałą A, wynosi ona w przybliżeniu 1,44225

Szukamy czasu wykonania dla N=9
(1,44225*9)^3=T
Po obliczeniu dla N=9 wychodzi T=2187

Odróżnijmy praktykę od teorii, choć w tych przypadkach teoria się, sprawdza dobrze.

• Dla małych liczb niekoniecznie/rzadko się zgadzają obliczenia.
• Pierwsze wykonanie(wykonania) w wielu językach jest (znacznie) bardziej kosztowne niż po "rozgrzaniu"
• algorytm ma koszt ogólny, choćby dla zera przypadków
• albo O(x) kosztu głównego algorytmu, ale O(n) kosztu jego prezentacji

Wiem, że to nie są żadne rewelacje dla doświadczonych programistów, ale chciałem napisać.

Złożoności nie powinno się używać do liczenia rzeczywistego czasu. Dla złożoności O(n^3) mogę mieć algorytm, który wykonuje dokładnie 10 n^3 + 10000 * n operacji. Nie dość, że twoją formułę trzeba pomnożyć razy 10 to jeszcze dla małych n koszt algorytmu jest zdominowany przez czynnik liniowy. Złożoność ma sens, jak szacujesz, czy algorytm nadaje się do danego problemu. Bez patrzenia w kod można wydedukować, że algorytm o złożoności O(n!) może mieć zastosowanie tylko dla bardzo małych N, a algorytm O(log n) raczej nie zaboli nas nawet dla ogromnych n rzędu liczba atomów we wszechświecie

nieletni17 napisał(a):

Cześć,
Jestem uczniem technikum i zacząłem się trochę uczyć o złożoności algorytmów.
Trochę nie rozumiem pewnego rozumowania. Załóżmy że mamy algorytm o złożoności n^3 i załóżmy że dla danych n=3 algorytm wykonuje się w 81sekund.
Jak mogę obliczyć ile czasu (przybliżony) zajmie wykonanie tego algorytmu dla danych np n=9 (3x większe)?

Czy odpowiedzią będzie tutaj 243sekund?
Czy ktoś mógłby mnie nakierować, albo może podrzucić jakieś strony które to tłumaczą?

Złożoność reprezentowana w notacji O(n) to tylko ukazanie zależności między ilością operacji jakie wykonuje się w algorytmie a ilością danych. Podkreślam w algorytmie. Czasu jako takiego się tu nie porusza.

Jak się zachowa czasowo program w którym wykorzysta się ów algorytm to już inna historia. Wiele czynników może bowiem różne implementacje algorytmów spowalniać.

Temat tego co może w praktyce je spowalniać to już wkraczanie na grunt takich zagadnień jak

1. architektura komputera

• pewne dane w ogólności lub w szczególnych przypadkach mogą być przetwarzane przez pewne maszyny szybciej, inne wolniej
• inny jest też czas wczytania/zapisu danych do pamięci RAM, inny na dysk, inny zaś jest czas dostępu do rejestrów procesora
• niektóre komputery mogą mieć układy obliczeniowe wykonujące pewne operacje szybciej niż inne przez co w praktyce nieco bardziej złożony algorytm może się dla interesującego nas zakresu danych wykonywać szybciej niż wymagający mniej kroków dla tego samego zbioru danych

2. architektura systemu operacyjnego

• mechanizmy przydzielania pamięci - wpływa np. na czas zapisu danych
• system plików - zapis/odczyt między systemami mogą się różnić
• sposób zarządania przez system operacyjny jednocześnie uruchomionymi programami
  3.architektura oprogramowania
• język jaki wybrano
• jak język implementuje różne operacje
• jak ty implementujesz w nim operacje - pewne funkcjonalnie równoważne rozwiązania można na różne sposoby zaprogramować

I inne, których nie jestem w stanie przytoczyć w tym momencie z głowy.