Porównywanie złożoności obliczeniowej

0

Cześć!
Mógłby mi ktoś pomóc w poniższych dwóch zadaniach?

  1. "Załóżmy, że porównujemy implementacje sortowania przez scalanie i sortowania przez wstawianie na tym samym komputerze. Dla danych wejściowych rozmiaru n sortowanie przez wstawianie działa w 8n^2 krokach, podczas gdy sortowanie przez scalanie wymaga wykonania 64n*lg n kroków. Dla jakich wartości n sortowanie przez wstawianie wygrywa z sortowaniem przez scalanie?"
  2. "Jaka jest najmniejsza wartość n, dla której algorytm wykonujący 100n2 operacji działa szybciej niż algorytm wykonujący 2n operacji na tym samym komputerze?"

Zadania te pochodzą z książki "Wprowadzenie do algorytmów" Thomasa Cormena.

0

A matematyke w szkole miał? o_O

  1. 8n^2 < 64n*log(n)
    i rozwiąż sobie tą nierówność
  2. 2n = 100*n2
    jw.
0

Matematykę w szkole miałem :P, ale jestem w 2 klasie gimnazjum, a nie 3 liceum. To, że taką równość oraz nierówność należy rozwiązać to ja wiem. Tylko nie wiem jak. Pierwszą przekształciłem do postaci n < 8 * log2(n). Drugą nie mam pojęcia jak przekształcić.

1

Jak nie potrafisz tego zrobić matematycznie to wpisz w excelu:
=8*LOG(WIERSZ();2)
w A1 i rozciągnij do A50

1 użytkowników online, w tym zalogowanych: 0, gości: 1