Co to jest logn?

Krótka wersja jest taka, że jest to termin z dziedziny informatyki, który również okazał się na tyle krótki, że spodobał mi się jako nazwa domeny. Wbrew temu, co inni mogą ci powiedzieć, nie jest to błędna pisownia „login”. Również, Itend to pronounce it as „log” followed by the letter „n”.

The long version is that it’s the term used to describea class of highly efficient algorithms.If you’ll indulge me in a short lesson…

Time Complexity

In computer science, algorithms are often compared by the amount of time or memory that they consume to perform a task. Aby uczynić te porównania sprawiedliwymi i łatwymi do zrozumienia, analizujemy je na podstawie zależności między rozmiarem zadania a liczbą kroków wymaganych do jego wykonania.

Na przykład, załóżmy, że chcesz uśrednić listę wartości liczbowych. Aby to zrobić, musiałbyś zsumować wszystkie liczby, a następnie podzielić je przez liczbę wartości, które posiadasz. Liczba kroków jest bezpośrednio związana z liczbą wartości: jeśli podwoisz liczbę wartości do uśrednienia, będziesz oczekiwał, że zajmie to dwa razy więcej czasu. Jest to przykład złożoności liniowej: wraz ze wzrostem liczby elementów (oznaczanej skrótem n) czas wykonania zadania rośnie w tym samym tempie.

Na pewno można to zrobić znacznie gorzej niż w czasie liniowym; wiele zadań wymaga czasu wielomianowego lub nawet wykładniczego! Sortowanie list liczb jest dobrym przykładem; musisz wykonać wiele przejść przez daneato przesiać wszystko do ostatecznej kolejności.

Jednakże istnieją również pewne algorytmy, które są lepsze niż czas liniowy. Rozważmy grę w zgadywanie, w której człowiek myśli o liczbie z przedziału od jednego do 100, a komputer musi zgadnąć, co to jest. Jeśli komputer zgadnie błędnie, człowiek mówi komputerowi, czy odpowiedź jest „wyższa” czy „niższa” od zgadywanej. Wybierając ostrożnie zgadywanie, ta informacja pozwala komputerowi wyeliminować połowę pozostałych liczb przy każdym zgadywaniu (przez wybieranie zawsze liczby pośrodku możliwego zestawu liczb).

Ponieważ każde zgadywanie dzieli pozostałą pulę liczb na pół, powtarzające się połówki łączą się i tworzą odwrotny wykładnik: alogarytm. Effectively, the number of steps to solve the problemgrows increases linearly as the problem space grows exponentially. Inaczej mówiąc, podwojenie rozmiaru problemu skutkuje tylko jednym dodatkowym krokiem (porównaj to z algorytmem liniowym, gdzie podwojenie rozmiaru problemu również podwaja liczbę kroków). Skrótowo nazywamy tę zależność logn, pokazując, że w miarę jak n (rozmiar problemu) staje się większe, liczba kroków jest tylko logarytmem tej liczby.

Tak więc, algorytmy logarytmiczne są bardzo wydajne i dobrze oceniane.Pomyślałem, że byłoby zabawnie nazwać moją domenę po nich.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.