Какво е голямото O на двоичното търсене?

2024 Автор: Lynn Donovan | [email protected]. Последно модифициран: 2023-12-15 23:43

Двоично търсене е по-бързо от линейно Търсене с изключение на малки масиви.

Двоично търсене алгоритъм.

Оттук нататък каква е сложността на двоичното търсене?

Двоично търсене работи в най-лошото логаритмично време, правейки O(log n) сравнения, където n е броят на елементите в масива, O е нотация с голямо O, а log е логаритъмът. Двоично търсене заема постоянно (O(1)) пространство, което означава, че пространството, заето от алгоритъма, е същото за произволен брой елементи в масива.

Освен това двоичното търсене ли е най-бързото? Да и не. да, има търсения които са средно по-бързи от разполовяване Търсене . Но аз вярвам, че те все още са O(lg N), само с по-ниска константа. Искате да сведете до минимум времето, необходимо за намиране на вашия елемент.

По подобен начин някой може да попита как се пише двоично търсене?

Двоично търсене : Търсене сортиран масив чрез многократно разделяне на Търсене интервал наполовина. Започнете с интервал, покриващ целия масив. Ако стойността на Търсене ключът е по-малък от елемента в средата на интервала, стеснете интервала до долната половина. В противен случай го стеснете до горната половина.

Каква е времевата сложност на двоичното търсене?

Така че трябва да има някакъв тип поведение, което алгоритъмът показва, за да му се даде а сложност на дневник n. Нека видим как работи. От двоично търсене има най-добра ефективност от O(1) и най-лошия случай (среден случай) ефективност на O(log n), ще разгледаме пример за най-лошия случай. Помислете за сортиран масив от 16 елемента.