Sumator - suma ciągu arytmetycznego Grasshopper Summation
Wpis z 05.06.2021, autor Andrzej Mazur · Codewars · Subskrybuj LekcjePHP na Youtube
Celem zadania jest napisanie funkcji, która zwróci sumę pierwszych n wyrazów ciągu arytmetycznego.
Czwarty odcinek i zadanie z programowania w języku PHP na website CodeWars.com, gdzie możemy poszerzać swoją wiedzę, rozwiązując zadania programistyczne.
Ja wybrałem język PHP i zadanie o nazwie: "Sumator - suma ciągu arytmetycznego" - (ang.) "Grasshopper Summation".
W zadaniu pokazano jak zadanie, pozornie do wykonania w pętli, należy wykonać za pomocą gotowego wzoru na obliczenie sumy ciągu arytmetycznego.
W czasie rozwiązywania poruszam temat złożoności obliczeniowej, która powinna być jak najmniejsza. Rozwiązanie w pętli da złożoność rzędu O(n) natomiast za pomocą wzoru na sumę ciągu arytmetycznego uzyskamy złożoność O(1).
Przedstawione zadanie, należy do jednych z tych jakie można otrzymać w ramach zadań rekrutacyjnych. Pozornie proste, może nas zwlec na manowce. Często tak jest, że znajomość Matematyki bywa niezbędna podczas programowania.
Kod źródłowy
function summation($n) {
// My code - My Solutions
return ($n*(1+$n)/2);
}Przykładowe złożoności obliczeniowe
Najczęstsza notacja to duże O, Ω (omega), czy Θ (theta)
Θ(1) - Złożoność stała - niezależnie od liczby danych wejściowych. Mówimy, że problem o złożoności Θ(1) możemy rozwiązać w stałym czasie niezależnie od wielkości danych wejściowych.
Θ(n) - Złożoność liniowa. Przypadek gdzie czas rozwiązania problemu jest wprost proporcjonalny do wielkości danych wejściowych.
Θ(n^2) - Złożoność kwadratowa. Jest to specyficzny przypadek złożoności wielomianowej. Gdzie czas rozwiązania problemu jest kwadratem ilości danych wejściowych.
Θ(log(n)) - Złożoność logarytmiczna, czas rozwiązania zależy od wyniku logarytmu z wielkości danych wejściowych.
Θ(n!) - Jest to złożoność typu silnia. Gdzie silnia z n to iloczyn wszystkich liczb od 1 do n. Na przykład 3! = 1 2 3 = 6.
To tylko najbardziej popularne przykłady. Z pozostałych to warto znać jeszcze:
- Ο(nlog(n)) - Złożoność liniowo-logarytmiczna,
- Ο(n^x) - Złożoność wielomianowa,
- Ο(x^n) - złożoność wykładnicza
Film przygotował dla Was:
Andrzej EZNAWCA Mazur
Zapraszam na moje strony:
LekcjePHP.pl
Eznawca.pl
