Mam taką treść zadania i osobiście mam problem z jego rozwiązaniem, albo nie jestem jego pewny, ze względu na słabą wiedzę z tego tematu, dlatego mam prośbę o naprowadzenie :/Algorytm wykonuje zadanie dla \(\displaystyle{ n=10}\) w czasie 1 sek, a zadanie \(\displaystyle{ n=100}\) w czasie 20sek.
Jaki wniosek mona wyciągnąć odnośnie złożoności czasowej tego algorytmu. Odpowiedź uzasadnij.
Mam tutaj wzór
\(\displaystyle{ t _{n} = c \cdot T \left( n \right)}\)
Jak dobrze rozumiem to tak:
\(\displaystyle{ t_n}\) - funkcja czasu wykonywania algorytmu(można to uznać jako zależność pomiędzy liczbą operacji elementarnych wykonywanych w trakcie przebiegu algorytmu a rozmiarze danych wyjściowych?)
\(\displaystyle{ C}\) - złożoność? Nie wiem za co tutaj odpowiada to C. Rząd złożoności?
\(\displaystyle{ T(n)}\) - funkcja z argumentem rozmiaru zadania dla algorytmu?(rozmiar zadania dla algorytmu?)
No więc tak, najpierw podkładam pod wzór pierwsze dane.
\(\displaystyle{ t_{n} = c \cdot T \left( n \right)}\)
\(\displaystyle{ t_{n} = c \cdot n^{2}}\) - Nie wiem jak tutaj dojść do tego co ma być podstawione pod tą funkcję z rozmiarem zadania, wydaje mi się, że jak dane są o wielkościach 10 i 100 to N do kwadratu będzie tu najlogiczniejsze, podejrzewam, że przy innych wartościach bym się po prostu pogubił.
\(\displaystyle{ 1 = c \cdot 100}\) 1 czyli 1 sekunda, 100 czyli 10 do kwadratu.
\(\displaystyle{ c = \frac{1}{100}}\)
\(\displaystyle{ t_{n} = \frac{1}{100} \cdot 100 = 1}\)
Teraz czas na n=100;
\(\displaystyle{ t_{n} = c \cdot T \left( n \right)}\)
\(\displaystyle{ t_n = \frac{1}{100} \cdot 100^{2}}\) - 1/100 było \(\displaystyle{ c}\) z \(\displaystyle{ n=10}\).
\(\displaystyle{ t_n = \frac{1}{100} \cdot 10 000}\)
\(\displaystyle{ t_n = 100}\)
I jaką mam tutaj odpowiedź udzielić i jaki wniosek?
Że algorytm posiada złożoność czasową kwadratową? szczerze nie wiem, i nie chcę dalej brnąć bo pewnie głupoty piszę
Bardzo proszę o pomoc.
