Złożoność potęgowania

Question

Witam, zacząłem nie dawno uczyć się Pythona i mam pytanie: jak to jest ze złożonością algorytmów w różnych językach, weźmy na przykład potęgowanie w C++ jak potęguje używam funkcji pow(), albo samemu piszę funkcję w stylu: 
 

int q_e(int n, int k){

	if (k == 0)	return 1;
	if (k == 1)	return n;

	if (k % 2 == 0)	return q_e(n, k/2) * q_e(n, k/2);
	else			return n * q_e(n, (k - 1)/2) * q_e(n, (k - 1)/2);
}

No i ona ma złożoność logarytmiczną... Za to w Pythonie mogę napisać po prostu: n ** k i teraz jak powinienem traktować taką instrukcje? Jako stałą? 

Pozdrawiam,

Answer 1

ja bym napisał tak żeby pomnożyła się tyle razy ile wpiszesz np 2 ma sie pmnożyć 6 razy czyli 2*2*2*2*2*2 potrzebna do tego biblioteka chyba match.h chyba tak.

Comments

math*
Nazwy bibliotek z reguły mają sens :P

---

Tylko po co skoro w math.h jest funkcja pow().

---

no własnie zapomniałem tego też może użyć

---

No, ja wiem, że jest funkcja pow() i wiem, że mogę napisać własną fukcje :) O obu wspomniałem w pytaniu... Pytanie dotyczyło tego czy złożoność operatora ** w Pythonie jest taka sama jak funkcji takiej w C++.

---

No nie sondze zeby ** dzialalo inaczej niz pow(). No bo jak inaczej podniesc do potegi?

Answer 2

Algorytm potęgowania jest na tyle mało złożony, że prawdopodobnie oba rozwiązania wyglądają podobnie.

Dziwne pytanie anyway.