Математическая логика и теория алгоритмов. Самохин А.В. - 84 стр.

UptoLike

ВУЗ: 

МГТУ ГА | Москва

Составители: 

Рубрика: 

84 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ
îÁ ÓÁÍÏÍ ÄÅÌÅ ÓÐÒÁ×ÅÄÌÉ×Ï ÇÏÒÁÚÄÏ ÂÏÌÅÅ ÓÉÌØÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ: ÓÕÝÅ-
ÓÔ×ÕÅÔ ÓÈÅÍÁ ÒÁÚÍÅÒÁ O(n log n) É ÇÌÕÂÉÎÙ O(log n), ÓÏÓÔÏÑÝÁÑ ÔÏÌØËÏ ÉÚ
ÜÌÅÍÅÎÔÏ× é É éìé, ËÏÔÏÒÁÑ ÉÍÅÅÔ n ×ÈÏÄÏ× É n ×ÙÈÏÄÏ× É ÏÓÕÝÅÓÔ×ÌÑ-
ÅÔ ÓÏÒÔÉÒÏ×ËÕ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ n ÎÕÌÅÊ É ÅÄÉÎÉà (ÜÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ ÎÁ
×ÙÈÏÄÅ ÓÔÏÌØËÏ ÖÅ ÅÄÉÎÉÃ, ÓËÏÌØËÏ ÎÁ ×ÈÏÄÅ, ÐÒÉÞ¾Í ×ÙÈÏÄÎÁÑ ÐÏÓÌÅÄÏ×Á-
ÔÅÌØÎÏÓÔØ ×ÓÅÇÄÁ ÎÅ×ÏÚÒÁÓÔÁÀÝÁÑ). ñÓÎÏ, ÞÔÏ ÓÒÅÄÎÉÊ ÂÉÔ ×ÙÈÏÄÁ × ÔÁËÏÊ
ÓÉÔÕÁÃÉÉ ÒÅÁÌÉÚÕÅÔ ÆÕÎËÃÉÀ ÂÏÌØÛÉÎÓÔ×Á.
ðÒÉ ËÁÖÕÝÅÊÓÑ ÐÒÏÓÔÏÔÅ ÆÏÒÍÕÌÉÒÏ×ËÉ ÅÄÉÎÓÔ×ÅÎÎÁÑ ÉÚ×ÅÓÔÎÁÑ ËÏÎ-
ÓÔÒÕËÃÉÑ ÔÁËÏÊ ÓÈÅÍÙ (ÓÏÒÔÉÒÕÀÝÁÑ ÓÅÔØ AKS, ÐÒÉÄÕÍÁÎÎÁÑ áÊÔÁÉ, ëÏÍ-
ÌÏÛÏÍ É óÃÅÍÅÒÅÄÉ ÓÒÁ×ÎÉÔÅÌØÎÏ ÎÅÄÁ×ÎÏ, × 1983 ÇÏÄÕ) ×ÅÓØÍÁ ÓÌÏÖÎÁ, É
ÐÏÑ×ÌÅÎÉÅ ËÁËÏÊ-ÔÏ ÂÏÌÅÅ ÐÒÏÓÔÏÊ ËÏÎÓÔÒÕËÃÉÉ ÂÙÌÏ ÂÙ ÚÁÍÅÞÁÔÅÌØÎÙÍ ÄÏ-
ÓÔÉÖÅÎÉÅÍ.
84                                    çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

   îÁ ÓÁÍÏÍ ÄÅÌÅ ÓÐÒÁ×ÅÄÌÉ×Ï ÇÏÒÁÚÄÏ ÂÏÌÅÅ ÓÉÌØÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ: ÓÕÝÅ-
ÓÔ×ÕÅÔ ÓÈÅÍÁ ÒÁÚÍÅÒÁ O(n log n) É ÇÌÕÂÉÎÙ O(log n), ÓÏÓÔÏÑÝÁÑ ÔÏÌØËÏ ÉÚ
ÜÌÅÍÅÎÔÏ× é É éìé, ËÏÔÏÒÁÑ ÉÍÅÅÔ n ×ÈÏÄÏ× É n ×ÙÈÏÄÏ× É ÏÓÕÝÅÓÔ×ÌÑ-
ÅÔ ÓÏÒÔÉÒÏ×ËÕ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ n ÎÕÌÅÊ É ÅÄÉÎÉà (ÜÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ ÎÁ
×ÙÈÏÄÅ ÓÔÏÌØËÏ ÖÅ ÅÄÉÎÉÃ, ÓËÏÌØËÏ ÎÁ ×ÈÏÄÅ, ÐÒÉÞ¾Í ×ÙÈÏÄÎÁÑ ÐÏÓÌÅÄÏ×Á-
ÔÅÌØÎÏÓÔØ ×ÓÅÇÄÁ ÎÅ×ÏÚÒÁÓÔÁÀÝÁÑ). ñÓÎÏ, ÞÔÏ ÓÒÅÄÎÉÊ ÂÉÔ ×ÙÈÏÄÁ × ÔÁËÏÊ
ÓÉÔÕÁÃÉÉ ÒÅÁÌÉÚÕÅÔ ÆÕÎËÃÉÀ ÂÏÌØÛÉÎÓÔ×Á.
   ðÒÉ ËÁÖÕÝÅÊÓÑ ÐÒÏÓÔÏÔÅ ÆÏÒÍÕÌÉÒÏ×ËÉ ÅÄÉÎÓÔ×ÅÎÎÁÑ ÉÚ×ÅÓÔÎÁÑ ËÏÎ-
ÓÔÒÕËÃÉÑ ÔÁËÏÊ ÓÈÅÍÙ (ÓÏÒÔÉÒÕÀÝÁÑ ÓÅÔØ AKS, ÐÒÉÄÕÍÁÎÎÁÑ áÊÔÁÉ, ëÏÍ-
ÌÏÛÏÍ É óÃÅÍÅÒÅÄÉ ÓÒÁ×ÎÉÔÅÌØÎÏ ÎÅÄÁ×ÎÏ, × 1983 ÇÏÄÕ) ×ÅÓØÍÁ ÓÌÏÖÎÁ, É
ÐÏÑ×ÌÅÎÉÅ ËÁËÏÊ-ÔÏ ÂÏÌÅÅ ÐÒÏÓÔÏÊ ËÏÎÓÔÒÕËÃÉÉ ÂÙÌÏ ÂÙ ÚÁÍÅÞÁÔÅÌØÎÙÍ ÄÏ-
ÓÔÉÖÅÎÉÅÍ.

Страницы