To będzie \(\displaystyle{ O(n\log n)}\). Można to udowodnić przez indukcję. Czyli dla pewnej stałej \(\displaystyle{ c>0}\) zachodzi
\(\displaystyle{ T(n) \leq c \cdot n \log n}\)
I tę stałą wyznaczasz w kroku indukcyjnym...
Znaleziono 4909 wyników
- 4 paź 2018, o 23:22
- Forum: Informatyka
- Temat: [Algorytmy] Równanie rekurencyjne
- Odpowiedzi: 6
- Odsłony: 1847
- 4 paź 2018, o 10:02
- Forum: Algebra abstrakcyjna
- Temat: Pokaż, że G ma min. 6 elementów
- Odpowiedzi: 6
- Odsłony: 951
Re: Pokaż, że G ma min. 6 elementów
Przykładowo, jeśli G ma 5 elementów, to z tw. Lagrange'a każdy jej element ma rząd 1 lub 5 . Skoro istnieje tylko jeden element rzędu 1 w G to istnieje element x\in G o rzędzie 5 . Wtedy e,x,x^2,x^3,x^4 to parami różne elementy w G , a zatem G=\{e,x,x^2,x^3,x^4\} . Innymi słowy G jest izomorficzna z...
- 3 paź 2018, o 21:43
- Forum: Kombinatoryka i matematyka dyskretna
- Temat: Ilość kombinacji w zbiorze z warunkiem sumy
- Odpowiedzi: 2
- Odsłony: 770
Ilość kombinacji w zbiorze z warunkiem sumy
Wzoru jawnego na liczbę takich kombinacji raczej nie uzyskasz, chyba, że dla jakichś konkretnych (małych) parametrów. Natomiast można napisać efektywny program który takie coś potrafi obliczyć, używając programowania dynamicznego.
- 7 lut 2016, o 12:58
- Forum: Informatyka
- Temat: [C] Dwa do dużej potęgi
- Odpowiedzi: 8
- Odsłony: 1401
[C] Dwa do dużej potęgi
Nie przyda się.
- 6 lut 2016, o 18:03
- Forum: Informatyka
- Temat: [C] Dwa do dużej potęgi
- Odpowiedzi: 8
- Odsłony: 1401
[C] Dwa do dużej potęgi
zmienna long long ma \(\displaystyle{ 64}\) bity, co oznacza, że największa liczba jaką pomieści to \(\displaystyle{ 2^{64}-1}\), musisz zaimplementować własną arytmetykę, jeśli chcesz operować na większych liczbach
- 6 lut 2016, o 17:28
- Forum: Topologia
- Temat: Prosta jako suma najwyżej przeliczalnie wielu odcinków
- Odpowiedzi: 2
- Odsłony: 610
Prosta jako suma najwyżej przeliczalnie wielu odcinków
Z wnętrza każdego nietrywialnego odcinka można wybrać liczbę wymierną.
- 25 sty 2016, o 20:44
- Forum: Algebra abstrakcyjna
- Temat: Grupy wolne
- Odpowiedzi: 3
- Odsłony: 947
Grupy wolne
Musiałbyś udowodnić, że 2^{\kappa_1}=2^{\kappa_2}\Rightarrow \kappa_1 = \kappa_2 , a to zdaje się nie wynika z ZFC. Ale to może teoriomnogościowcy powinni się wypowiedzieć. edit: to wyżej chyba nie ma sensu, ale nie będę usuwał edit2: |\bigoplus_{x \in X} \ZZ|=|X| jeśli tylko |X|\geq \omega , więc m...
- 23 sty 2016, o 00:41
- Forum: Algebra abstrakcyjna
- Temat: Grupy wolne
- Odpowiedzi: 3
- Odsłony: 947
Grupy wolne
Żeby odróżnić skończone \(\displaystyle{ F_k}\) od siebie oraz skończone od \(\displaystyle{ F_{\omega}}\) można użyć argumentu, który przytoczyłeś. Dla \(\displaystyle{ \kappa>\omega}\) mamy \(\displaystyle{ |F_{\kappa}|=\kappa}\), więc już moce odróżniają te grupy...
- 24 gru 2015, o 21:15
- Forum: Teoria liczb
- Temat: Dla jakich n liczba jest kwadratem
- Odpowiedzi: 6
- Odsłony: 967
Dla jakich n liczba jest kwadratem
Rozkład nie jest potrzebny (ani możliwy), ale można zauważyć, że różnica pomiędzy dwoma kolejnymi kwadratami staje się od pewnego miejsca większa niż \(\displaystyle{ 12}\), dlatego wystarczy rozważyć tylko kilka przypadków.
- 2 gru 2015, o 19:45
- Forum: Teoria liczb
- Temat: Formuła odwrotna dla funkcji multiplikatywnych
- Odpowiedzi: 7
- Odsłony: 1020
Formuła odwrotna dla funkcji multiplikatywnych
Już została udzielona. Jeśli chodzi Ci o wzór jawny, to czasem istnieje, czasem nie. Nie ma reguły.
- 2 gru 2015, o 15:37
- Forum: Teoria liczb
- Temat: Formuła odwrotna dla funkcji multiplikatywnych
- Odpowiedzi: 7
- Odsłony: 1020
Formuła odwrotna dla funkcji multiplikatywnych
Wzór powyżej jest niepoprawny, powinno być \(\displaystyle{ \mu(d)}\)
- 26 lis 2015, o 00:46
- Forum: Szeregi liczbowe i iloczyny nieskończone
- Temat: Zbieżność szeregu z definicji
- Odpowiedzi: 1
- Odsłony: 634
Zbieżność szeregu z definicji
\(\displaystyle{ \sum_{k=1}^n q^k = \frac{q-q^{n+1}}{1-q}}\)
- 12 lis 2015, o 18:59
- Forum: Hyde Park
- Temat: Funkcja dzeta riemanna
- Odpowiedzi: 65
- Odsłony: 9917
Funkcja dzeta riemanna
Gratuluję, rozbawiłeś mnieAlthorion pisze:To chyba nie jest aż taki wielki problem. W liceach uczą chyba wyłącznie byli studenci matematyki, a tacy powinni posiadać wymaganą wiedzę,
- 12 lis 2015, o 00:49
- Forum: Hyde Park
- Temat: Funkcja dzeta riemanna
- Odpowiedzi: 65
- Odsłony: 9917
Funkcja dzeta riemanna
Pomijając na chwilę kwestię "po co?". Kto miałby o tym uczyć? Nauczyciele, których cała wiedza ogranicza się do znajomości zadań ze zbioru?
- 2 lis 2015, o 23:54
- Forum: Algebra abstrakcyjna
- Temat: Rozszerzenia ciał.
- Odpowiedzi: 10
- Odsłony: 1255
Rozszerzenia ciał.
Można przez indukcję udowodnić, że zbiór:
\(\displaystyle{ \{ \prod_{i\in S}p_i: S\subseteq \{1,2,...,n\}\}}\) jest bazą
\(\displaystyle{ \{ \prod_{i\in S}p_i: S\subseteq \{1,2,...,n\}\}}\) jest bazą