«Тікелей таңдау» әдісін талдау. Кілттерді салыстырулар саны С кілттердің алғашқы орналасу санына тәуелсіз. Осы тұрғыдан қарастыратын болсақ, бұл әдіс тікелей қосуға қарағанда табиғилау болып табылады. С үшін:
C=(n2-n)/2. Ең аз орын ауыстырулар саны:
Mmіn=3*(n-1) Алғашқы реттелген кілттер жағдайында
Mmax= n2/4+3*(n-1) –ге тең болады, егер алғашқы кілттер кері ретпен орналасқан болса. Енді Mave–ны анықтау үшін алгоритм массивті қарастырады. Бұ алгоритмде жаңадан табылған ең кіші шамамен әрбір элементті салыстырып отырады. Егер ол ібіріншіден кіші болса онда меншіктеу командасы орындалады. Екінші элементтің бірінші элементтен кіші болу ықтималдылығы ½-ге тең. Осы ықтималдылықтан минимумға меншіктеу ықтималдылығы шығады. Үшінші элементтің алғашқы екі элементтен кіші болу ықтималдылығы 1/3-ге тең, ал төртінші элементтің алдыңғы үш элементтен кішіболу ықтималдылығы – ¼ және т.с.с. Сондықтан толық күтілетін сілтеме саны - Нn-1, мұндағы Нn – үйлесімділік саны:
Нn= 1+1/2+1/3+....+1/ n.
Нn-ді былай өрнектеуге болады:
Нn= ln n + g + 1/2 n – 1/ 12 n2 + ...
Мұндағы g = 0.577216... – Эйлер тұрақтысы деп аталады. N саны айтарлықтай көп болған жағдайда бөлшек сандарды жойып жіберуімізге (ескермеуімізге) болады. Сондықтан і-тексеруде меншіктеулердің орташа санын аппроксимациялауға болады.
Ғ = ln і + g + 1. Таңдаулы сұрыптаудағы Ғі қосынды і 1-ден n-ге дейін өзегергендегі орташа сан
Mavg = n* (g + 1) +(Si:1<=i<=n :ln i).
Сөйтіп жуық мәнін аламыз:
Mavg ≈ n* (ln (n)+ g ). Бұдан тікелей қосумен салыстырғанда тікелей таңдау алгоритмі тиімділеу. Дегенмен егер кілттер бастапқы жағдайдың өзінде–ақ реттелген болса, онда тікелей қосу жылдам орындалады.
