HiAsm

Вверх ↑

Форумы "Игра в слова"Теоретический вопрос про оптимизацию ← Ctrl12 3Ctrl →

Ответов: 9906

Рейтинг: 351

#1: 2017-05-26 23:17:52 ЛС | профиль | цитата

-= DriveR =- писал(а):

но хотелось бы понять что вы сказали.

Вот спрашивается, чего тут непонятного:

procedure THiAsmClass.doCalc;
var i,j,k,l:integer;
    ss:string;
begin
  ss := ToString(_Data);
  _hi_CreateEvent(_Data, @onIs, ss);
  i := 0; j := _Numb-1;
  k := StrComp(pchar(_Arr[i]), pchar(ss));
  l := StrComp(pchar(_Arr[j]), pchar(ss));
  if (k=0)or(l=0) then exit;
  if (k<0)and(l>0) then while (j-i)>1 do begin
    k := (i+j) div 2;
    l := StrComp(pchar(_Arr[k]), pchar(ss));
    if l=0 then exit;
    if l>0 then j := k
    else i := k;
  end;
  _hi_CreateEvent(_Data, @onNo, ss);
end;

Пять простеньких строк внутри цикла ......

Каждое сравнение уменьшает область (между i и j) поиска слова в отсортированном массиве в ДВА РАЗА.
Поэтому, сколько надо сделать сравнений для массива в 1000 слов ??? Десять.
А для массива в 2000 слов -- одиннадцать.
А для массива в 4000 слов -- двенадцать.
И т.д.. Это и есть логарифмическая асимптотика.

А сколько надо сделать сравнений для массива в 1000 слов полным перебором ???
Разницу чувствуете, или как

карма: 9

Редактировалось 3 раз(а), последний 2017-05-26 23:28:03

Форумы "Игра в слова"Теоретический вопрос про оптимизацию ← Ctrl12 3Ctrl →