zadanie nick: Mógłby ktoś rozpisać tak aby wyszło θ(n²): f₂(n) = lognⁿ + 0,1n²

Kejt: Wg mnie nie ma tu czego rozpisywać. Mamy sumę funkcji, lognⁿ rośnie wolniej niż n² (stałe możemy pominąć), zatem przy obliczaniu bierzemy pod uwagę jedynie n². Zatem całość to theta(n²).

nick: ale jak to tak po prostu można pominąć lognⁿ?

Kejt: Masz określić tempo wzrostu f₂ jak rozumiem. Przy obliczaniu bierzesz zawsze ten najbardziej decydujący czynnik, czyli funkcję, która rośnie najszybciej, bo to ona określa tempo wzrostu całego wyrażenia. Na jaki to przedmiot? Tak z ciekawości.

nick: ok dzięki, programowanie

Kejt: Proszę, ale pamiętaj, że to pomijanie działa tylko przy dodawaniu.

nick: f₁(n) = 0,01√4ⁿ + 100n² a jak taką funkcję przekształcić aby otrzymać θ(2ⁿ)?

Kejt: (i odejmowaniu)

Kejt: Matematyka na poziomie gimnazjum 4ⁿ = 2²ⁿ i wyciągasz ładnie pierwiastek. Dalej już wiesz?

nick: pierwiastek z tego to 2ⁿ

Kejt: Tak. Dalej robisz jak pisałam wcześniej.

nick: A jeszcze mam taką funkcję: f(n) = 2 w potędze(log₂√n i dalej jest + logn¹⁰⁰ Ma wyjść: θ(n^1/2)

Kejt: jak rozumiem chodzi o 2^log₂√n + log_n100 próbowałeś to uprościć? wzory na logarytmy znasz? co według Ciebie rośnie szybciej, logarytm, czy funkcja wykładnicza?

nick: tak o taki przykład chodzi, szybciej rośnie funkcja wykładnicza

nick: aha z logarytmu wyjdzie √n + 100log_n

Kejt: Uprość 2^log₂√n Tutaj są wzory: 218

Kejt: Tak.

nick: A jeśli mam następującą funkcję: int F(n) {if(n == 1) return 1; else return F(n−1) + 3n * n − 3n+1;} To jak obliczyć rząd funkcji czyli to co przed chwilą wyznaczaliśmy ?

Kejt: Tu już tak różowo nie jest, trzeba wyznaczyć równania rekurencyjne. Równania typu "jeden krok w tył":

	⎧	c, gdy n=0,
T(n) =	⎨
	⎩	aT(n−1)+d(n), gdy n>0.

Kejt: Jeśli masz do tego odpowiedź, to mogę spróbować rozwiązać, ale w przeciwnym wypadku nie gwarantuję poprawnego rozwiązania.

nick: nie posiadam niestety, ale dzięki

Kejt: To mam coś w tym rzeźbić?