     [" ࠪ⨪㬠   (1 )". ⮤᪠ ࠧࠡ⪠ (-
⠢⥫ ..䮭  ..騪). - .: , 1992.  N3.]
    
        N3.  " " ( ᪠).

          
    ॡ  ॠ  ⮤ ஢, ।塞 ਠ-
⮬ ,  ஢  ᯥਬ⠫쭮 ࠢ.
     "஢"  㯮冷祭 ⮢ ᫥⥫-
 x[1], x[2], ..., x[n] (n>1)  뢠, ..  ⠪  -
  ⮢, ᫥ ன 㤥 믮 ᫮ x[i]<=x[i+1]
  i.  ⢥ ⮢ x[i] ᯮ짮   23.11.16,
9.5.97  ..
    ࠢ ॠ ⮤ ஢ 㦭 ஢   -
      ᫥⥫쭮.  ᬮ ᫥⥫-
 ࠧ  (ਬ, n=10, 20, 50, 100), ᯮ  
n  ࠩ  ᫥騥 室 ⠭ ⮢:
    -  㦥 㯮冷祭  뢠;
    -  㯮冷祭  ⭮ 浪 ( ⠭);
    -  砩 ⠭ ⮢.
    業 ⮤ ந  ᫥騬 ६ ࠬࠬ:
    1) ᫮ ࠢ  ⮢  ᫥⥫쭮,  믮  
        㯮冷祭;
    2)  ᫮  ६饭 (   ⮢,  뫮
       ⮢    -  ᨬ  ⮤),  믮-
          㯮冷祭;
    3) ६ ࠡ 楤 ஢.
      ᯥਬ⮢  ନ     ⠡, ਬ,
⠪ ଠ:

                 < ⮤ ஢>
  ----------------------------------------------------------
  |  n |   ࠬ  |  ᫥⥫쭮 | ।  |
  |    |             |   1     2     3      4   | 祭 |
  ----------------------------------------------------------
  | 10 | ࠢ   |   9    45    33     25   |    28    |
  |    | ६饭 |          ...             |   ...    |
  |    | ६       |                          |          |
  ----------------------------------------------------------
  | 20 | ࠢ   |          ...             |   ...    |
  |    |   ...       |                          |          |
                 
    
           (⮤ ஢)
    ⮤ 1-5 - ,   (᫮ ࠢ 浪  n*n),
⮤ 6-10 - ᫮,   (浪 n*log2(n)).   -
      [1], ஬ ⮤ 4.  ᪮ 㪠  
 ᯨ    ࠭,      ਢ  ᠭ
 ⮤.
  1) ஢ 묨 ⠢ ([1] 101-103; [3] 95-96).
  2) ஢ 묨 ⠢ ([1] 103-104; [3] 97-98).
  3) ⮤ 쪠 ([1] 130-132; [2] 27-28; [3] 101-102).
  4) 筠 ஢ ([2] 30-31).
  5) ஢ ।⢮ ⮣ 롮  ([1] 169-171;  [2] 15-16;
     [3] 99-100).
  6) ⮤  ([1] 105-107; [2] 37-40; [3] 105-107).
  7)  ஢, ४ᨢ ਠ ([3] 114-117).
  8)   ஢,  ४ᨢ  ਠ  ([1]  140-144;  [2]
     88-97; [3] 114-121).
  9) ஢    ⥢  ᫨ﭨ   ([1]  198-199;   [2]
     106-111).
 10) ஢ ⢥ ⥢ ᫨ﭨ  ([1] 193- 197;  [2]
     12-117).
         
    
           
    1. ࠢ  ⮢ ()   ॠ    
᪮  㭪樨,  ६饭 (  뫪) ⮢ - 
 楤.   䥪, 㭪  楤   -
 祭 () 稪 ࠢ  ६饭, ᮮ⢥-
⢥.
    2.      । ⮤ ஢ ॠ  
楤   ࠬ஢: ᨢ (x),  ஬ 砫 室
㯮冷祭 ᫥⥫쭮,    ࠡ 楤  
  㯮冷祭 ᫥⥫쭮,   (n) 㯮冷稢-
 ᫥⥫쭮.  楤   ࠢ쭮  ࠡ  
 n<=100.
    ० 祬 ஢ ᯥਬ, ᫥ ⫠   
楤 (ਬ,  - ᫥⥫쭮  10).
    3. ᭮ ணࠬ  ஢  室 ᫥-
⥫쭮,   楤ࠬ ஢   ⠡ -
⮢.
    砭:  ஢ ᯥਬ⮢    -
 ஢  !
             
    
          
    1. ⠭  ( ਠ).
    2. ᠭ   ॠ ⮤ ஢.
    3. ⨭ ணࠬ  몥 ᪠.
    4.  ஢ 楤 ஢.
    5.   १⠬ ᯥਬ⮢.
                                            

         
    1.    . ⢮ ணࠬ஢  .  3. - .: ,
1978.
    2. ਭ . ஢  ⥬ ஢. - .: 㪠, 1983.
    3.  .    . - .: , 1989.
    
    
            

        
      ⮤ ஢  ⠢:    ࠭  㯮冷祭
᫥⥫쭮  x[1],  x[2],  ..., x[k-1] ⠢ x[k] ⠪,
⮡ 㯮冷祭묨  k  ⮢ 室  ᫥-
⥫쭮.
     ᨬ  ᯮᮡ ᪠    q=x[k] ࠧ-
 ᫥騥 ⮤.
    )  .  稭 q   । ࠢ  x[k-1],
x[k-2], ... ᫨ q>x[i],  x[i] ᤢ    (i+1)-      q
ࠢ  x[i-1],  q ⠢  (i+1)- .
    )  .  稭 q ࠢ  । ⮬
᫥⥫쭮 x[1], x[2], ..., x[k-1].  ᫨  q    ⮣
,     q  ⥬  ᯮᮡ    -
᫥⥫쭮,  ᫨  -  ࠢ .   
q 㤥 , ࠢ ( ⮣ )  ᤢ    
 ࠢ,   ᢮  ⠢ q.

        
     ⮤ ஢  ⠢  ⮢,  -
    ண.
      ᨬ  浪 ॡ ⠪  ࠧ ᫥騥
⮤.
    )  .   । ᬠਢ   ᥤ -
⮢  (x[1]   x[2], x[2]  x[3], x[3]  x[4]  ..)   㯮冷-
祭  (x[i]>x[i+1]) ⠢ ;  १  -
ᨬ    ᢮ ⥫쭮  -   -
⥫쭮.   筠 楤 ਬ  ᥬ -
⠬, ஬ ᫥. (砭:  ᫨    ।  ᬮ
᫥⥫쭮    뫮    ⠭,  ᫥⥫-
 㦥 㯮冷祭  ᫥ ४ ஢.)
    )   (⮤ ᥨ).  ⠪ ࠢ-
  x[i]  x[i+1] (i=1, 2, ...),  ⮫쪮  㦥 㯮-
冷祭  x[k]>x[k+1].  ⮬ 砥  "㯮冷祭"  
x[k+1]  稭  ࠢ  ⠢  ⠬ x[k], x[k-1],
x[k-2], ...   ,     㯮冷祭  ᫥-
⥫쭮   k+1  ⮢.   ᬮ -
।: ࠢ  x[k+1]  x[k+2], x[k+2]  x[k+3]  ..

        
     ஢ 롮஬  -     頥  
᢮ ⥫쭮 ,  ⠪   .
    ᭮ ࠧ ⮩  - ஢  롮஬: -
室    (ᨬ)   ᫥⥫쭮   
⠢   (᫥) ⮬;  ⠢訬 -
 㯠 筮.
    
        
     k - 楫  1  n/2. ᨬ   㣠 㯮冷稢-
 (  ᠭ  ⮤) ᫥⥫쭮   -
⮢,    㣠  k 権:
        x[i], x[i+k], x[i+2k], ...   (i=1, 2, ..., k)
⥬ k 㬥蠥    . ᫥ 蠣 
믮  k=1.
    祭 k   ࠧ묨 ᯮᮡ,    ⠪: -
砫  k  ࠢ  (楫  ) n/2,  ⥬ k  ࠧ 㬥蠥
.
                                                            
        
    롨ࠥ   (ਬ, ।)      
᫥⥫쭮 ⠢ ⠪, ⮡ ࠭  -
   ᢮ ⥫쭮 , .. ⮡ ᫥   뫨 ⮫쪮
訥  ࠢ  ,  ࠢ - 訥  ࠢ.  ⥬
   ⮤ ਬ    ࠢ  ᫥⥫쭮.
(砭: ᫨    - ,   㯮冷稢
 ᫥   ᯮᮡ.)
    ॡ㥬  ⠭  ⮢  믮 ᫥騬 ࠧ:
᫥⥫쭮 ᬠਢ ᫥ ࠢ,     
, 訩  ࠢ ࠭,  ᬠਢ ࠢ -
   , 襣 ࠭;    ⠢,
᫥ 祣 ᬮ ᫥⥫쭮   殢 த.
      ஢  ॠ ४ᨢ    ४ᨢ.
  ஬ 砥 ࠭   ⥩ ( -  ) -
⥫쭮   ⥪,  㣠    㯮冷稢
ᠭ  ᯮᮡ.   㤥 㯮冷祭,  ⥪ 
࠭ ࢮ   ⥯  㯮冷稢 ⥬  ᯮᮡ.
                                                            
        
    ᭮  ⠪ ஢ - ࠧ  ᫥⥫쭮  
᪮쪮 㦥 㯮冷祭 ᫥⥫쭮⥩ (  "१-
")  ⥬ ꥤ      १,   -
  㯮冷祭 ᫥⥫쭮. ⬥⨬,   ⮬
室 ⥫쭠  (ᨢ y[1..n]).
    ᫨    蠣 ᫨  १,  ⠪ ᫨ﭨ -
 ⥢.  ⮬ 砥   뤥  ᫥騥  ਠ
஢ ᫨ﭨ.
    )  .  砫 १  ᫥⥫-
   ,   ᫨  १    ⮢
( x[1]  x[2],  x[3]  x[4], ...),  ७  ᨢ y.
  ஬ ⠯ ᥤ १ (y[1], y[2]  y[3], y[4]; y[5], y[6]
 y[7], y[8]; ...) ꥤ  १  4 ⮢,   -
뢠   ᨢ x.  쥬 ⠯  १  8 -
⮢     ᨢ y,  .. (砭: ,   
殢 㯮冷祭     ᨢ x).
    )  .     ( 뢠)
१  砫 ᨢ x    (⠪  뢠, 
  ᬮ ࠢ ) १   ᨢ,   ᫨
  १,  뢠  砫 ᨢ y. ⥬  ᫨-
  ᫥騥 ᨬ쭮  १   殢,  祭-
 १ 뢠 (ࠢ )   ᨢ y.   
浪  १ ᫥ ᫨ﭨ 뢠 ᭮  砫 y (᫥ 
 ꥤ १), ⢥ -   y (।  -
ꥤ १)  ..  ⠯ ஢ 稢, 
   x  ७ᥭ  ᨢ y.  ஬ ⠯  ਬ-
      楤, ⮫쪮 ᨢ x  y  ஫ﬨ.  ⠪
.
