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

Szukaj
Najnowszy film
Youtube logoSumator - suma ciągu arytmetycznego
Popularne Tagi