ЗНАЙ ИНТУИТ, Лекция, Търсене

Последователно търсене

За последователно търсене в таблицата приемаме, че има указател, чиято стойност принадлежи на сегмента или, вероятно,. На този указател са разрешени само следните операции; първоначално му присвоява стойността 1 или (или, ако е по-удобно, 0 или, увеличава и/или намалява с един и го сравнява с 0, 1 или. С такива конвенции най-очевидният алгоритъм за намиране на първото появяване на дадено име в таблицата е Алгоритъм 13.1. Тук, както и при всички други алгоритми за търсене, описани в тази лекция, приемаме, че алгоритъмът спира незабавно след намиране или установяване, че таблицата не съдържа.

Алгоритъм 13.1. Последователно търсене

намерено: показва, че не е намерено: не е включено в

Нека разгледаме някои аспекти на ефективността на последователното търсене, започвайки със стандартни техники за програмиране. В програма, изградена като един цикъл, като Алгоритъм 13.1, всяко значително ускорение трябва да се дължи на подобрения в кода в цикъла. За да видите какви операции се извършват в цикъла, е необходимо да пренапишете алгоритъм 13.1 във форма, близка до машинния език:

За една итерация се изпълняват до четири инструкции: две сравнения, едно увеличение и едно прехвърляне.

За да се ускори вътрешният цикъл, често срещан трик е добавянето на специални редове към таблицата, които правят незадължително изричното проверяване дали указателят е достигнал границите на таблицата. Това може да се направи в алгоритъм 13.1. Ако преди търсене добавим желаното име в края на таблицата, тогава цикълът винаги ще завършва с намиране на запис; по този начин не е нужно да правим проверката всеки път в цикъла. В края на цикъла проверете условието n "style =" display: inline; ">, изпълнява се само веднъж, казва дали намереният запис е истински или специален запис в таблицата. Това е показано в алгоритъм 13.2.

Алгоритъм 13.2. Подобрено последователно търсене

Подобрението на алгоритъм 13.1 ще бъде най-очевидно, ако пренапишем алгоритъм 13.2 в същата машинна нотация, използвана преди:

По време на всяка итерация се извършват само три действия вместо четири, както беше в Алгоритъм 13.1. По този начин в повечето изчислителни устройства цикълът в алгоритъм 13.2 ще работи много по-бързо, отколкото в алгоритъм 13.1, и тъй като скоростта на контура определя скоростта на цялата програма, същото съпоставяне се извършва и за двете програми.

Тъжното е, че трикът с добавяне в края на таблицата преди търсенето успява само ако имаме директен достъп до края на таблицата. Това е възможно, ако таблицата се съхранява в памет с произволен достъп, но обикновено не е възможно при използване на верижно разпределение или последователна памет. .

Алгоритъм 13.3 Последователно търсене на таблица, съхранявана в естествен ред

Логаритмично търсене в статични таблици

Говорим за логаритмичното време на търсене веднага щом стане възможно, във време, независимо от, да се намали последователно задачата за търсене в таблица, съдържаща имена, до задача за търсене в таблица, съдържаща не повече от имена, където е константа. В този случай времето, необходимо за търсене в таблицата с имена, удовлетворява връзката на повтаряемостта

Най-често срещаните предположения, които правят възможно намаляването на размера на таблица от до за време, независимо от това, е, че пространството от имена е линейно подредено и че сравнението на две имена от (за определяне на y) "style =" display: inline; "> е елементарна операция, която изисква постоянно количество време, независимо от. В резултат на това времето, необходимо за повечето логаритмични алгоритми за търсене, естествено се измерва с броя на сравненията (с три резултата) на двойки имена. За някои алгоритми обаче сравненията с големи са по-естествени, но фиксиран брой резултати.

В този раздел ние разглеждаме само статични таблици, т.е. таблици, в които включва и изключва или не се появяват, или са толкова редки, че когато се появят, се изгражда нова таблица. Структурите на динамични таблици, които позволяват логаритмично време за търсене, както и ефективни алгоритми за включване и изключване, са разгледани в края на тази глава. За статичните таблици трябва да се обсъждат само алгоритмите за търсене и изграждане на таблици. Алгоритмите за търсене са достатъчно прости, но някои от алгоритмите за изграждане на таблици са сложни. Тази ситуация възниква, защото в случай на статична таблица е разумно да се считат честотите за достъп като известни и може да си струва да се отделят значителни усилия за изграждане на оптимална таблица - таблица с минималното средно време за търсене (спрямо дадени честоти на достъп). Алгоритмите за изграждане на таблици и техния анализ са най-важните теми в този раздел.