Разработка технологии создания дистанционных курсов на примере курса "Администрирование DB2", страница 28

3.3 Выбор оптимального алгоритма, реализующего процедуру "DeleteBadCharacters", используя метод O - оценок

При создании части программы, отвечающей за логический контроль SQL выражений, для реализации  процедуры удаления мусора из SQL строки и приведения ее к стандартному для разбора виду, -  возникла идея двух алгоритмов для ее написания.

Для выбора наиболее подходящего с точки зрения наименьшего времени выполнения алгоритма реализации процедуры "DeleteBadCharacters" воспользуемся методом O-оценок. В данном случае N - средняя длина строки SQL запроса.

Рассмотрим код первого варианта:

procedure TSQLFormX.DeleteBadCharacters;

var i,j, lng:integer;

   text:ansistring;

begin

  sqltext:=UpperCase(Memo2.Lines.Text);

  lng:=length(sqltext);

  setlength(sqltext,2*lng);

  i:=1;

  while i<lng do begin

    if (sqltext[i]=#13) or (sqltext[i]=#10) or (sqltext[i]=#0) then begin

      sqltext[i]:=' ';

    end;

    if (sqltext[i-1]='(') or (sqltext[i-1]=')') or (sqltext[i-1]='>') or (sqltext[i-1]='=') then

      if sqltext[i]<>' ' then begin

        for j:=lng+1 downto i+1 do

          sqltext[j]:= sqltext[j-1];

        sqltext[i]:=' ';

        inc(lng);

      end;

    if (sqltext[i-1]='!') and (sqltext[i]<>'=') or (sqltext[i-1]='<') and (sqltext[i]<>'>') then begin

      for j:=lng+1 downto i+1 do

        sqltext[j]:= sqltext[j-1];

      sqltext[i]:=' ';

      inc(lng);

    end;

  if (sqltext[i]=' ') and (i=1) then begin

    for j:=i+1 to lng do

      sqltext[j-1]:= sqltext[j];

    Dec(lng);

  end

  else if sqltext[i]=' ' then

     if sqltext[i-1]=' ' then begin

       for j:=i+1 to lng do

         sqltext[j-1]:= sqltext[j];

       Dec(lng);

     end;

  if i>1 then

    if ((sqltext[i]='(') or (sqltext[i]=')')) then begin

      if sqltext[i-1]<>' ' then  begin

        for j:=lng+1 downto i do

          sqltext[j]:= sqltext[j-1];

        sqltext[i]:=' ';

        inc(lng);

      end;

    end;

  inc(i);

end;

SetLength(sqltext,lng);

end;

Сложность процедуры "DeleteBadCharacters" для данного варианта алгоритма составляет:

O(B)=O(1); O(C)=O(1); O(E)=O(1); O(F)=O(1);

O(G)=O(1); O(H)=O(1); O(M)=O(1); O(P) =O(1);

O(S)=O(1); O(RR) =O(1); O(Y)=O(1); O(Z) =O(1);

O(CC)=O(1);

O(I)=O(N*O(E))=O(N); O(K)=O(N*O(G))=O(N);

O(L)=O(N*O(M))=O(N); O(R)=O(N*O(S))=O(N);

O(X)=O(N*O(Y))=O(N);

O(D)=O(1)*(O(I)+O(F))=O(N);

O(T)=O(1)*(O(I)+O(H))=O(N);

O(Q)= O(1)*O(L)+O(1)*O(R)=O(N);

O(BB)=O(1)*(O(X)+O(Z))=O(N);

O(EE)=O(N)*(O(C)+O(D)+O(T)+O(Q)+O(BB)+O(CC)=O(N)*(O(1)+O(N)+O(N)+O(N)+O(N)+O(1))=O(N*N)=O(N²);

O(A)=O(B)+O(EE)+O(HH) = O(1)+O(N²)+O(1) = O(N²);

Таким образом сложность данной реализации процедуры "DeleteBadCharacters" равна O(N²)

Теперь рассмотрим код второго варианта:

procedure TSQLFormX.DeleteBadCharacters;

var i,j:integer;

    wasSpace:boolean;

begin

  sqltext:=Memo2.Text;

  SetLength(sqltext,Length(Memo2.Text)+40);

  wasSpace:=false;

  i:=1;

  j:=1;

  while Memo2.text[i]=' ' do

    inc(i);

  dec(i);

  while i<=Length(Memo2.Text) do begin

       inc(i);

       if (Memo2.Text[i]=' ') then begin

           if wasSpace then

             continue

           else begin

              wasSpace:=true;

              sqltext[j]:=' ';

              inc(j);

              continue;

           end;

       end;

       if (Memo2.Text[i]=#13) then begin

          if wasSpace then

             continue

          else begin

             sqltext[j]:=' ';

             wasspace:=true;

             inc(j);

             continue;

          end;

       end;

       if (Memo2.Text[i]=#10) then begin

         if wasSpace then

           continue

         else begin

           sqltext[j]:=' ';

           wasspace:=true;

           inc(j);

           continue;

         end;

       end;

       wasSpace:=false;

       if Memo2.Text[i]='(' then begin

         if (j>1) and (sqltext[j-1]=' ') then

           dec(j);

         sqltext[j]:=' ';

         inc(j);

         sqltext[j]:=Memo2.Text[i];