Диссертация (1104114), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

³¤¥¬¨­²¥°¥±®¢ ²¼±¿ ±«³· ©­»¬¨ ¯ ° ¬¨ hxn ; yni, ². ¥. ² ª¨¬¨ ¯ ° ¬¨, ·²®K (xn; yn) = log Pn + O(log n). Ž²¬¥²¨¬, ·²® ¢ ±«³· ¥ k = 1, m = 3 ¬»¯®«³· ¥¬ ª®­±²°³ª¶¨¾ ¨§ [13].74 ° ¬¥²° ¬¨ ¤ ­­®© ª®­±²°³ª¶¨¨ ¿¢«¿¾²±¿ ·¨±« m ¨ k, ² ª¦¥° §¬¥°» ¯®«¥© Fn. „ «¥¥ ¬» ¢»¡¥°¥¬ ² ª¨¥ §­ ·¥­¨¿ ¯ ° ¬¥²°®¢, ·²®±«®¦­®±²¨ xn ¨ yn ¡³¤³² ¡«¨§ª¨ ª n; ¢¥«¨·¨­ I (xn : yn) ¡³¤¥² § ¢¨±¥²¼®² ®²­®¸¥­¨¿ k ¨ m.  ¨¡®«¥¥ ¨­²¥°¥±¥­ ±«³· ©, ª®£¤ k ¢»¡¨° ¥²±¿¡«¨§ª¨¬ ª m=2, ².

ª. ¯°¨ ½²®¬ ¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ xn ¨ yn ®ª §»¢ ¥²±¿¡«¨§ª®© ª n.°¨ ´¨ª±¨°®¢ ­­»µ §­ ·¥­¨¿µ ¯ ° ¬¥²°®¢ ¢±¿ª®¥ ±«®¢® xn ±«®¦­®±²¨ n ¬®¦­® ° ±±¬ ²°¨¢ ²¼ ª ª ª®¤ ±«³· ©­®£® k-¬¥°­®£® ¯®¤¯°®±²° ­±²¢ ¨§ Vn. „«¿ «¾¡®£® k-¬¥°­®£® ¯®¤¯°®±²° ­±²¢ xn ­ ©¤¥²±¿ ®°²®£®­ «¼­®¥ ¥¬³ k-¬¥°­®¥ ¯°®±²° ­±²¢® yn ² ª®¥, ·²® ³±«®¢­ ¿±«®¦­®±²¼ K (ynjxn) ¨¬¥¥² ¬ ª±¨¬ «¼­³¾ ¢®§¬®¦­³¾ ¢¥«¨·¨­³ (²®·­¥¥,K (ynjxn) ¥±²¼ «®£ °¨´¬ ·¨±« k-¬¥°­»µ ¯®¤¯°®±²° ­±²¢ ¢ Vn, ®°²®£®­ «¼­»µ ¯®¤¯°®±²° ­±²¢³ xn). ˆ¬¥¥² ¬¥±²® ®¤­®°®¤­®±²¼: ¢±¥ k-¬¥°­»¥¯®¤¯°®±²° ­±²¢ ®°²®£®­ «¼­» ®¤¨­ ª®¢®¬³ ·¨±«³ k-¬¥°­»µ ¯®¤¯°®±²° ­±²¢. ®½²®¬³ ¯®«³·¥­­ ¿ ¯ ° hxn; yni ¡³¤¥² ±«³· ©­®©, ². ¥.

¡³¤¥²¨¬¥²¼ ±«®¦­®±²¼ log Pn + O(log n). —²®¡» ¯®«³·¨²¼ ¤®ª § ²¥«¼±²¢® ²¥®°¥¬» 8, ®±² ¥²±¿ ¯®ª § ²¼, ·²® ¤«¿ ±«³· ©­»µ ¯ ° ®°²®£®­ «¼­»µ ¯®¤¯°®±²° ­±²¢ ¢»¯®«­¿¥²±¿ ²¥®°¥¬ 7 (­¥«¼§¿ ¬ ²¥°¨ «¨§®¢ ²¼ ¢§ ¨¬­³¾¨­´®°¬ ¶¨¾). „®ª § ²¥«¼±²¢® ½²®£® ´ ª² (³²¢¥°¦¤¥­¨¥ 6) ¨ ¿¢«¿¥²±¿®±­®¢­»¬ °¥§³«¼² ²®¬ ¤ ­­®£® ° §¤¥« .„®ª § ²¥«¼±²¢® ®±­®¢ ­® ­ ±«¥¤³¾¹¥¬ ±¢®©±²¢¥ ®°²®£®­ «¼­»µ ¯®¤¯°®±²° ­±²¢.  ±±¬®²°¨¬ £° ´ Gn, ¢¥°¸¨­ ¬¨ ª®²®°®£® ¿¢«¿¾²±¿ ¢±¥k-¬¥°­»¥ ¯®¤¯°®±²° ­±²¢ ¨§ Vn.

¥¡° ¬¨ ¢ £° ´¥ ¡³¤³² ±®¥¤¨­¥­» ®°²®£®­ «¼­»¥ ¯®¤¯°®±²° ­±²¢ . ‡ ´¨ª±¨°³¥¬ ­¥ª®²®°³¾ ¢¥°¸¨­³ £° ´ v0.  ±±¬®²°¨¬ ±«³· ©­®¥ ¡«³¦¤ ­¨¥ ­ £° ´¥, ­ ·¨­ ¾¹¥¥±¿ ¢ v0 .³±²¼ vi { ¢¥°¸¨­ £° ´ , ¯®«³·¥­­ ¿ ¯®±«¥ i ¸ £®¢ ±«³· ©­®£® ¡«³¦¤ ­¨¿. „«¿ ª ¦¤®£® i ±«³· ©­ ¿ ¢¥«¨·¨­ vi ° ±¯°¥¤¥«¥­ ­ ¬­®¦¥±²¢¥¢¥°¸¨­ Gn (². ¥. ­ ¬­®¦¥±²¢¥ k-¬¥°­»µ ¯®¤¯°®±²° ­±²¢ Vn). Œ» ¯®ª ¦¥¬, ·²® ¤«¿ ­¥ª®²®°®£® s ° ±¯°¥¤¥«¥­¨¥ vs ¡«¨§ª® ª ° ¢­®¬¥°­®¬³.°¨ ½²®¬ s § ¢¨±¨² ®² m ¨ k, ­® ­¥ ®² n.ˆ² ª, ¯³±²¼ ¤«¿ ª ¦¤®£® n ±«®¢ xn ¨ yn ª®¤¨°³¾² ±«³· ©­³¾ ¯ °³®°²®£®­ «¼­»µ k-¬¥°­»µ ¯®¤¯°®±²° ­±²¢ ¨§ Vn. ¥°¥©¤¥¬ ª ´®°¬ «¼­®¬³ ¤®ª § ²¥«¼±²¢³.Š®«¬®£®°®¢±ª¨¥ ±«®¦­®±²¨ ¨ ¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ x,° ±²³² «¨­¥©­® ¯® n:‹¥¬¬ 15.K (xn) = (mk k2)jFnj + O(log n);75y(4.4)K (yn) = (mk k2 )jFnj + O(log n);(4.5)2I (xn : yn) = k jFnj + O(log n):(4.6)„®ª § ²¥«¼±²¢®.

³±²¼ W { «¨­¥©­®¥ ¯°®±²° ­±²¢® ­ ¤ Fn .  ©¤¥¬·¨±«® ¯®±«¥¤®¢ ²¥«¼­®±²¥© e1; e2; : : : ; ek , ±®±²®¿¹¨µ ¨§ k «¨­¥©­® ­¥§ ¢¨±¨¬»µ ¢¥ª²®°®¢ ¯°®±²° ­±²¢ W .Ž¡®§­ ·¨¬ s = dim(W ) ¨ N = jFnj. ‚ ª ·¥±²¢¥ e1 ¬®¦­® ¢§¿²¼ «¾¡®© ­¥­³«¥¢®© ¢¥ª²®° W . ’ ª¨¬ ®¡° §®¬, ¤«¿ ¢»¡®° ¯¥°¢®£® ¢¥ª²®° ¢ ¯®±«¥¤®¢ ²¥«¼­®±²¨ ¨¬¥¥²±¿ N s 1 ¢ °¨ ­². ³±²¼ ¢¥ª²®° e1 ³¦¥ ¢»¡° ­. ’®£¤ ¤«¿ ¢»¡®° ¢²®°®£® ¢¥ª²®° ¯®±«¥¤®¢ ²¥«¼­®±²¨ ¨¬¥¥²±¿(N s N ) ¢ °¨ ­²®¢, ¯®±ª®«¼ª³ e2 ­¥ ¤®«¦¥­ «¨­¥©­® § ¢¨±¥²¼ ®² e1. „ «¥¥, ¥±«¨ ¢»¡° ­» ¯¥°¢»¥ i ¢¥ª²®°®¢ ¯®±«¥¤®¢ ²¥«¼­®±²¨, ²® ¢ ª ·¥±²¢¥¢¥ª²®° ei+1 ¬®¦¥² ¡»²¼ ¢§¿² «¾¡®© ¢¥ª²®°, ­¥ «¥¦ ¹¨© ¢ «¨­¥©­®©®¡®«®·ª¥ e1; : : : ; ei.

’. ¥. ¤«¿ ¢»¡®° ei+1 ¨¬¥¥²±¿ N s N i ¢ °¨ ­²®¢.‘«¥¤®¢ ²¥«¼­®, ¢ ¯°®±²° ­±²¢¥ W ¨¬¥¥²±¿(N s 1)(N s N ) : : : (N s N k 1) = N ks(1 + O(1=N ))¯®±«¥¤®¢ ²¥«¼­®±²¥© ¨§ k «¨­¥©­® ­¥§ ¢¨±¨¬»µ ¢¥ª²®°®¢. ®¤±² ¢«¿¿¢¬¥±²® s ·¨±«® m, ­ µ®¤¨¬ ª®«¨·¥±²¢® ¯®±«¥¤®¢ ²¥«¼­®±²¥© ¨§ k «¨­¥©­® ­¥§ ¢¨±¨¬»µ ¢¥ª²®°®¢ ¢® ¢±¥¬ ¯°®±²° ­±²¢¥ Vn. „ «¥¥, ¯®¤±² ¢«¿¿¢¬¥±²® s ·¨±«® k, ­ µ®¤¨¬ ª®«¨·¥±²¢® ¯®±«¥¤®¢ ²¥«¼­®±²¥© ¨§ k «¨­¥©­®­¥§ ¢¨±¨¬»µ ¢¥ª²®°®¢ ¢ ª ¦¤®¬ k-¬¥°­®¬ ¯®¤¯°®±²° ­±²¢¥ Vn. Ž²­®¸¥­¨¥ ½²¨µ ¢¥«¨·¨­Qn = N mk k (1 + O(1=N ))¤ ¥² ª®«¨·¥±²¢® k-¬¥°­»µ ¯®¤¯°®±²° ­±²¢ ¢ Vn. ‡ ¬¥²¨¬, ·²®K (xn) log Qn + O(log n); K (yn) log Qn + O(log n):(4.7)„ «¥¥ ¬» ¯®ª ¦¥¬, ·²® ¤«¿ ±«³· ©­®© ¯ °» ®°²®£®­ «¼­»µ ¯°®±²° ­±²¢¤ ­­»¥ ­¥° ¢¥­±²¢ ®¡° ¹ ¾²±¿ ¢ ° ¢¥­±²¢ .…±«¨ ¯®¤¯°®±²° ­±²¢® xn ³¦¥ § ¤ ­®, ²® yn «¥¦¨² ¢ ¯®¤¯°®±²° ­±²¢¥ ¢¥ª²®°®¢ Vn, ®°²®£®­ «¼­»µ xn.  §¬¥°­®±²¼ ½²®£® ¯®¤¯°®±²° ­±²¢ ° ¢­ (m k).

® ¢® ¢±¿ª®¬ (m k)-¬¥°­®¬ ¯°®±²° ­±²¢¥ ¨¬¥¥²±¿Tn = N (m k)k k (1 + O(1=N ))k-¬¥°­»µ ¯®¤¯°®±²° ­±²¢. ‘«¥¤®¢ ²¥«¼­®, ¤«¿ «¾¡®© ¯ °» ®°²®£®­ «¼­»µ ¯®¤¯°®±²° ­±²¢ hxn ; yniK (xnjyn) log Tn + O(log n); K (xnjyn) log Tn + O(log n): (4.8)2276‚ ¯°®±²° ­±²¢¥ Vn ¨¬¥¥²±¿ (Qn Tn) ¯ ° ®°²®£®­ «¼­»µ k-¬¥°­»µ¯°®±²° ­±²¢. ®±ª®«¼ª³ ¯ ° hxn ; yni ¢»¡¨° ¥²±¿ ±«³· ©­®©,K (xn ; yn) = log Qn + log Tn + O(log n):„ «¥¥, ¯®±ª®«¼ª³ ±«®¦­®±²¼ ¯ °» K (xn; yn) ± ²®·­®±²¼¾ ¤® «®£ °¨´¬¨·¥±ª®£® ±« £ ¥¬®£® ° ¢­ K (xn)+ K (ynjxn) ¨ K (yn)+ K (xnjyn), ­¥° ¢¥­±²¢ (4.7) ¨ (4.8) ¤«¿ ±«³· ©­®© ¯ °» hxn ; yni ®¡° ¹ ¾²±¿ ¢ ° ¢¥­±²¢®.‘«¥¤®¢ ²¥«¼­®,I (xn : yn) = K (xn ) + K (yn) K (xn; yn) + O(log n) = log( QT n ) + O(log n):n¥¯®±°¥¤±²¢¥­­»¥ ¢»·¨±«¥­¨¿ «®£ °¨´¬®¢ Qn ¨ Tn ¤®ª §»¢ ¾² ²°¥¡³¥¬®¥ ³²¢¥°¦¤¥­¨¥. 2³¤¥¬ ±·¨² ²¼ m, k ¨ Fn (jFnj = 2(n) ) ¢»¡° ­­»¬¨ ² ª¨¬¨, ·²®K (xn) = n + O(log n);(4.9)K (yn) = n + O(log n);(4.10)I (xn : yn) = an + O(log n);(4.11)£¤¥ a { ­¥ª®²®° ¿ ¯®«®¦¨²¥«¼­ ¿ ª®­±² ­² .

’ ª¨¬ ®¡° §®¬, ¢§ ¨¬­ ¿¨­´®°¬ ¶¨¿ xn ¨ yn ° ±²¥² «¨­¥©­® ¯® n. ¥²°³¤­® § ¬¥²¨²¼, ·²® ª®£¤ ®²­®¸¥­¨¥ k=m ±²°¥¬¨²±¿ ª 1=2, ±®®²¢¥²±²¢³¾¹¥¥ §­ ·¥­¨¥ a ±²°¥¬¨²±¿ª ¥¤¨­¨¶¥. ‘«¥¤®¢ ²¥«¼­®, ¢»¡¨° ¿ §­ ·¥­¨¿ ¯ ° ¬¥²°®¢ m ¨ k, ¬®¦­®±¤¥« ²¼ ¢¥«¨·¨­³ a ±ª®«¼ ³£®¤­® ¡«¨§ª®© ª ¥¤¨­¨¶¥.®ª ¦¥¬, ·²® ³ ¯®±²°®¥­­»µ ¯®±«¥¤®¢ ²¥«¼­®±²¥© xn , yn ­¥«¼§¿ ¬ ²¥°¨ «¨§®¢ ²¼ ¢§ ¨¬­³¾ ¨­´®°¬ ¶¨¾, ².

¥. ¤«¿ ­¨µ ¢»¯®«­¿¥²±¿ ³²¢¥°¦¤¥­¨¥ ²¥®°¥¬» 7.„«¿ ¯®±²°®¥­­»µ ¯®±«¥¤®¢ ²¥«¼­®±²¥© x, y ¨ ¤«¿¢±¿ª®© ¯®±«¥¤®¢ ²¥«¼­®±²¨ z, ª®²®° ¿ ¯°®±² ®²­®±¨²¥«¼­® x ¨ ®²­®±¨²¥«¼­® y, ¢»¯®«­¥­® ° ¢¥­±²¢® K (zn) = O(log n).“²¢¥°¦¤¥­¨¥ 6.³±²¼ zn { ¯®±«¥¤®¢ ²¥«¼­®±²¼ ±«®¢ ¯°®±²»µ ®²­®±¨²¥«¼­® xn ¨ yn, ². ¥. K (znjxn) = O(log n) ¨ K (znjyn) = O(log n).„®ª ¦¥¬, ·²® K (zn) = O(log n). ‡ ´¨ª±¨°³¥¬ ­ ²³° «¼­®¥ n. „ «¥¥ ¤«¿¯°®±²®²» ®¡®§­ ·¥­¨© ¡³¤¥¬ ®¯³±ª ²¼ ­¨¦­¨© ¨­¤¥ª± n ¢±¾¤³, £¤¥ ½²®­¥ ¯°¨¢¥¤¥² ª ¯³² ­¨¶¥.„®ª § ²¥«¼±²¢®.77®±ª®«¼ª³ z ¯°®±²® ®²­®±¨²¥«¼­® x ¨ y,K (xjz ) = K (x; z ) K (z ) + O(log n) == K (x) + K (z jx) K (z ) + O(log n) == K (x) K (z ) + O(log n):(4.12)€­ «®£¨·­»¥ ¢»·¨±«¥­¨¿ ¬®¦­® ¯°®¢¥±²¨ ¤«¿ y.

®«®¦¨¬D = maxfK (xjz ); K (yjz )g:Ž²¬¥²¨¬, ·²® jK (xjz ) K (yjz )j = O(log n). ‚ ­®¢»µ ®¡®§­ ·¥­¨¿µK (xjz ) D; K (yjz ) D:„ «¥¥ ¬» ¤®ª ¦¥¬, ·²® ±³¹¥±²¢³¥² ¤®±² ²®·­® ¬­®£® ±«®¢, ±«®¦­®±²¼ª®²®°»µ ®²­®±¨²¥«¼­® z ­¥ ¯°¥¢®±µ®¤¨² D ( §­ ·¨², ·¨±«® D ¤®±² ²®·­® ¢¥«¨ª®). ®«¥¥ ²®·­®, ¯®ª ¦¥¬, ·²® D = K (x) O(log n). ²®¡³¤¥² §­ ·¨²¼, ·²® ³±«®¢­ ¿ ±«®¦­®±²¼ K (xjz ) ®·¥­¼ ¬ «® ®²«¨· ¥²±¿®² ¡¥§³±«®¢­®© ±«®¦­®±²¨ K (x).

„ «¥¥, ¨±¯®«¼§³¿ (4.12), ¬» ¯®«³·¨¬«®£ °¨´¬¨·¥±ª³¾ ®¶¥­ª³ ­ ±«®¦­®±²¼ z .‚ ¤®ª § ²¥«¼±²¢¥ ¡³¤³² ° ±±¬ ²°¨¢ ²¼±¿ ¶¥¯®·ª¨ ¯®¤¯°®±²° ­±²¢ {ª®­¥·­»¥ ¯®±«¥¤®¢ ²¥«¼­®±²¨x0 y1 x1 y2 : : : yr xr ;(4.13)£¤¥ xi, yi { k-¬¥°­»¥ ¯®¤¯°®±²° ­±²¢ Vn, ¯°¨·¥¬ «¾¡»¥ ¤¢ ±®±¥¤­¨µ¢ ¶¥¯®·ª¥ ¯®¤¯°®±²° ­±²¢ ®°²®£®­ «¼­». ®¤¯°®±²° ­±²¢® x0 ¡³¤¥¬­ §»¢ ²¼ «¥¢»¬ ª®­¶®¬, ¯®¤¯°®±²° ­±²¢® xr { ¯° ¢»¬ ª®­¶®¬ ¶¥¯®·ª¨. —¨±«® r ­ §®¢¥¬ ¤«¨­®© ¶¥¯®·ª¨ (r ­¥ § ¢¨±¨² ®² n). ³¤¥¬¨­²¥°¥±®¢ ²¼±¿ ²®«¼ª® ² ª¨¬¨ ¶¥¯®·ª ¬¨, ¢ ª®²®°»µ x0 = x.

’ ª ¿¶¥¯®·ª ¿¢«¿¥²±¿ ²° ¥ª²®°¨¥© ±«³· ©­®£® ¡«³¦¤ ­¨¿ ­ £° ´¥ Gn. Ž²¬¥²¨¬, ·²® ·¨±«® ¸ £®¢ ¡«³¦¤ ­¨¿ ·¥²­®, ­¥·¥²­»¥ ¸ £¨ ®¡®§­ ·¥­»xi (i = 0; 1; : : : ; r), ·¥²­»¥ ¸ £¨, ±®®²¢¥²±²¢¥­­®, yi (i = 1; : : : ; r).‘«³· ©­®¥ ¡«³¦¤ ­¨¥ ­ £° ´¥ ±®®²¢¥²±²¢³¥² ° ¢­®¬¥°­®¬³ ° ±¯°¥¤¥«¥­¨¾ ­ ¬­®¦¥±²¢¥ ¶¥¯®·¥ª ± ´¨ª±¨°®¢ ­­»¬ «¥¢»¬ ª®­¶®¬.  ¢­®¬¥°­®¥ ° ±¯°¥¤¥«¥­¨¥ ­ ¶¥¯®·ª µ ¨­¤³¶¨°³¥² ­¥ª®²®°®¥ ° ±¯°¥¤¥«¥­¨¥­ ¬­®¦¥±²¢¥ ¨µ ¯° ¢»µ ª®­¶®¢. Œ» ¯®¤¡¥°¥¬ ² ª®¥ §­ ·¥­¨¥ ¯ ° ¬¥²° r, ·²® ¯®«³· ¥¬®¥ ° ±¯°¥¤¥«¥­¨¥ ­ ¬­®¦¥±²¢¥ ¯° ¢»µ ª®­¶®¢ ¶¥¯®·¥ª ®ª ¦¥²±¿ ¡«¨§ª¨¬ ª ° ¢­®¬¥°­®¬³. ‚ ²® ¦¥ ¢°¥¬¿, ¬» ¯®ª ¦¥¬, ·²®± ¤®±² ²®·­® ¡®«¼¸®© ¢¥°®¿²­®±²¼¾ ¯° ¢»© ª®­¥¶ ±«³· ©­® ¢»¡° ­­®©78¶¥¯®·ª¨ ¨¬¥¥² ±«®¦­®±²¼ ­¥ ¡®«¥¥ D ®²­®±¨²¥«¼­® z . ˆ±¯®«¼§³¿ ½²®,¬» ¤®ª ¦¥¬, ·²® ·¨±«® ¯° ¢»µ ª®­¶®¢ ¶¥¯®·¥ª, ¨¬¥¾¹¨µ ±«®¦­®±²¼ ­¥¡®«¥¥ D ®²­®±¨²¥«¼­® z , ¢¥«¨ª®.°¥¦¤¥ ¢±¥£® ¯®ª ¦¥¬, ·²® ¤«¿ ¯®«¨­®¬¨ «¼­®© ¤®«¨ ¢±¥µ ¶¥¯®·¥ª¢¨¤ (4.13) ±«®¦­®±²¼ ¯° ¢®£® ª®­¶ xr ¬ « ®²­®±¨²¥«¼­® z .r‹¥¬¬ 16.

³±²¼ X { ¬­®¦¥±²¢® ¢±¥µ ¶¥¯®·¥ª ¢¨¤ (4.13). ’®£¤ ·¨±«® ² ª¨µ ¶¥¯®·¥ª, ¤«¿ ¯° ¢»µ ª®­¶®¢ ª®²®°»µ ¢»¯®«­¥­® ­¥° ¢¥­±²¢®K (xr jz ) D;jX r jpoly(n)(£¤¥ poly(n) { ­¥ª®²®°»© ¬­®£®·«¥­).„®ª § ²¥«¼±²¢®. „®ª ¦¥¬ ¡®«¥¥ ±¨«¼­®¥ ³²¢¥°¦¤¥­¨¥. € ¨¬¥­­®,¯®ª ¦¥¬, ·²® ­¥ ¬¥­¥¥ ·¥¬ ¯®«¨­®¬¨ «¼­³¾ ¤®«¾ ±®±² ¢«¿¾² ¶¥¯®·ª¨¯®¤¯°®±²° ­±²¢, ¤«¿ ª®²®°»µ ¢»¯®«­¿¾²±¿ ±«¥¤³¾¹¨¥ ¤¢ ³±«®¢¨¿: ) ¢±¥ ½«¥¬¥­²» ¶¥¯®·ª¨ xi, yi ¨¬¥¾² ±«®¦­®±²¼ ­¥ ¡®«¥¥ D ®²­®±¨²¥«¼­® z ;¡) ª ¦¤ ¿ ¯ ° ±®±¥¤­¨µ (¢ ¶¥¯®·ª¥) ¯®¤¯°®±²° ­±²¢ hyj ; xj i ¨«¨hxj ; yj+1i ±«³· ©­ , ². ¥.

¨¬¥¥² ±«®¦­®±²¼ ­¥ ¬¥­¼¸¥ log Pn O(log n)(§¤¥±¼ ¨ ¤ «¥¥ ¬» ¯®«¼§³¥¬±¿ ®¡®§­ ·¥­¨¿¬¨ ¨§ ¤®ª § ²¥«¼±²¢ ³²¢¥°¦¤¥­¨¿ 15).Ž²¬¥²¨¬, ·²® ¯ ° hyj ; xj i ¨¬¥¥² ±«®¦­®±²¼ ¡«¨§ª³¾ ª Pn ²®£¤ ¨²®«¼ª® ²®£¤ , ª®£¤ ±«®¦­®±²¼ K (xj ) ¡«¨§ª ª log Qn, ³±«®¢­ ¿ ±«®¦­®±²¼ K (yj jxj ) ¡«¨§ª ª log Tn. ’®·­¥¥, ±«³· ©­®±²¼ ¯ ° hyj ; xj i ½ª¢¨¢ «¥­²­ ²®¬³, ·²® ¤«¿ ­¥ª®²®°®© ª®­±² ­²» C ¢»¯®«­¥­» ­¥° ¢¥­±²¢ K (xj ) log Qn C log n;K (yj jxj ) log Tn C log n:„®ª § ²¥«¼±²¢® «¥¬¬» ¯°®¢¥¤¥¬¯® ¨­¤³ª¶¨¨ ¯® ¤«¨­¥ ¶¥¯®·ª¨.ijjX³±²¼ ¨¬¥¥²±¿ ­¥ ¬¥­¥¥ nc ¶¥¯®·¥ª ¤«¨­» i, ³¤®¢«¥²¢®°¿¾¹¨µ ³±«®¢¨¾ «¥¬¬». ‚»¡¥°¥¬ «¾¡³¾ ¨§ ­¨µ ¨ ° ±±¬®²°¨¬ ¢±¥ ¢®§¬®¦­»¥ ¥¥¯°®¤®«¦¥­¨¿ : : : yi+1 xi+1. °¨ ½²®¬ ¯®¤¯°®±²° ­±²¢® yi+1 ¤®«¦­®¡»²¼ ®°²®£®­ «¼­® xi, xi+1 { ®°²®£®­ «¼­® yi+1.

Характеристики

Список файлов диссертации