Walczę, żeby wypełnić tę tabelę, nawet jeśli wziąłem rachunek niedawno i dobry w matematyce. Jest określony tylko w rozdziale, jak radzić sobie z LIM (N ^ K / C ^ N), ale nie mam pojęcia, jak porównać inne funkcje. Sprawdziłem podręcznik rozwiązania i brak informacji na ten temat, tylko stół z odpowiedziami, które zapewnia niewielki wgląd.

enter image description here

1
Iaroslav Baranov 22 listopad 2020, 18:20

1 odpowiedź

Najlepsza odpowiedź

Kiedy rozwiązuję te, tak naprawdę nie myślę o limitach - opieram się na kilku faktach i dobrze znanych właściwości big-o notacji.

p. p.

ε ε ε-1. -Ε.

Fakt 3:

  • Jeśli f (n) ≤ g (n) + O (1), następnie 2 f (n) = o (2 g (n) ).
  • Jeśli f (n) ≤ g (n) - ω (1), następnie 2 f (n) = o (2 g (n) ).
  • Jeśli f (n) ≥ g (n) - O (1), następnie 2 f (n) = ω (2 g (n) ).
  • Jeśli f (n) ≥ g (n) + Ω (1), następnie 2 f (n) = Ω (2 g (n) ).

Fakt 4: LG (N!) = Θ (n lg (n)). Dowód wykorzystuje przybliżenie Stirling.

Aby rozwiązać (A), użyj faktu 1, aby zwiększyć obie strony do mocy 1 / K i zastosować fakt 2.

k lg (n) k n lg (c) n

grzech (n)

Aby rozwiązać (D), obserwuj, że N ≥ N / 2 + Ω (1) i zastosuj fakt 3.

lg (c) lg (n) lg (c) lg (c) lg (n) lg (n)

n

0
David Eisenstat 22 listopad 2020, 16:39