Pomoc ze zrozumieniem złożoności szeregu harmonicznego

Cześć!
Robiąc zadanie natrafiłem na opis który tylko wspominał o tym że szereg harmoniczny ma złożoność O(n * log(n)). Szukałem w internecie ale nie potrafię znaleźć jakiegoś wyjaśnienia skąd bierze się taka złożoność. Czy któś mógłby mi podrzucić jakiś link, albo wytłumaczyć skad O(n * log(n))?

Gdzie znalazłeś, że ma nlogn? Ja tu widzę złożoność n, (suma, n elementów).
https://www.geeksforgeeks.org/program-to-find-sum-of-harmonic-series/

https://stackoverflow.com/questions/25905118/finding-big-o-of-the-harmonic-series

@Suchy702:

Być może coś źle zrozumiałeś. Suma ciągu harmonicznego jest rzędu O(log n) [Nie algorytm obliczania sumy, tylko ilość operacji, które przybierają postać ciągu harmonicznego]. Często podczas analizy algorytmu występuje z innym czynnikiem, który jest liniowy i stąd wychodzi O(n log n)

@Suchy702:
Nie znam kontekstu, ale wygrzebałem kod rozwiązania i tam jest tak

		for(int i = 1; i<=n; i++) 
			for(int j = i*2; j<=n; j += i)
				if(a[i]<a[j])
					f[j] = max(f[j],f[i]+1);

Pierwsza pętlą ma n obrotów.
Druga pętla jest uzależniona od poprzedniej pętli, ma zmienną liczbę obrotów, robi n/i - 2*i obrotów. Liczby obrotów wewnętrznej pętli to n-2, n/2-4, n/3-6, .... Sumujesz to by mieć złożoność całego algorytmu. 1/i jest wyrazem ciągu harmonicznego, więc znasz górne ograniczenie sumy ∑1/i.

Szereg harmoniczny jest konceptem matematycznym.
Złożoność obliczeniowa to jest koncept informatyczny opisujący jak się skaluje czas wykonania danej implementacji czegoś.

Ergo pisanie szereg harmoniczny ma złożoność O(n log(n)) ma taki sam sens jak pytanie "jakie jest ciśnienie wewnątrz okręgu" (bez sprecyzowania o co chodzi z tym okręgiem nie ma to sensu).

Jeśli miałbyś kod (implementację) obliczającą szereg harmoniczny, to wtedy można mówić o złożoności.

Inna interpretacja, to można mówić, że szereg harmoniczny ma asymptotyczne tempo wzrostu: O(log n)

Suchy702 napisał(a):

Czy któś mógłby mi podrzucić jakiś link, albo wytłumaczyć skad O(n * log(n))?

Żeby na to odpowiedzieć potrzebne są konkrety. Musiałeś pominąć jakieś istotne szczegóły.
Jedyna implementacja obliczająca szereg harmoniczny jaka przychodzi mi do głowy ma złożoność liniową.