Złożoność czasowa i pamięciowa

Witam
Szukałem informacji na internecie dot. tego tematu, ale nie znalazłem odpowiedzi konkretnych - jakie mnie interesują.

Dajmy na to mamy prostą funkcję do podniesienia liczby do kwadratu :

int potega(int n) {
  int i = 1,s = 1;
  while(i<n) {
    s = s +2*i + 1;
    ++i;
  }
  return s;
} 

Złożoność obliczeniowa : 2 + 2(n-1) , ponieważ mamy w funkcji 2 operacje przypisania, po czym pętlę , która wykona się n - 1 razy a w niej 2 operacje.
**Złożoność obliczeniowa asymptotyczna ** : O(n)

Złożoność pamięciowa : 3 , ponieważ w funkcji wykorzystujemy 3 zmienne : n , i , s

I tutaj się pojawiają moje wątpliwości, ponieważ słyszałem o złożoności pamięciowej asymptotycznej. W jakich przypadkach miałaby ona wystąpić ? :O

Będę wdzięczny za przeanalizowanie mojego toku myślenia i wskazanie błędów.

dodanie znacznika <code class="cpp"> - fp

W twoim przypadku O(1) czyli tzw złożonośc stała.

1.A mógłbym prosić o jakiś przykład, w którym złożoność pamięciowa będzie O(n) ?
2.Czy samą deklarację zmiennej (bez przypisania do niej wartości) powinniśmy dodawać do złożoności obliczeniowej ?

1. Mnóstwo jest takich przykładów... Np. jeśli danych wejściowych jest n i musisz je zapisać w jakiejś tablicy, to jest to taka złożoność. Jakiś konkretny przykład, to wyszukiwanie maksimum z podanego ciągu n liczb.
2. Teoretycznie chyba tak (jeśli chcesz wiedzieć jaką złożoność ma Twój program), ale przy obliczaniu złożoności bierze się zwykle pod uwagę sam algorytm, a nie jego implementację w konkretnym języku, więc nie ma czegoś takiego, że jest sobie jakaś nieużywana a zadeklarowana zmienna. No i po co w ogóle mieć zadeklarowaną i nieużywaną zmienną w kodzie, który chcesz analizować? Wystarczy usunąć jej deklarację i po problemie. :P

@lukashid O(n)? Zmodyfikuj swoją funkcję tak, żeby nie zwracała tylko n² ale żeby zwróciła kwadraty wszystkich liczb 1..n Wynikiem będzie tablica o n elementach, więc pamięciowa złożoność to będzie O(n)

Ad.1 Czyli rozumiem, że wtedy kiedy uzależniamy liczbę zmiennych w (np. tablicy) od n. to będziemy mieli już O(n) złożoność pamięciową. Ale to nawiązując do przykładu z wyszukiwaniem maksimum O(n) będziemy mieli wtedy kiedy liczba elementów w tablicy do przeszukania będzie miała n elementów. Dobrze rozumiem ?

Tak.