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

Подождите немного. Документ загружается.

§3. óÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ× 71

ïÄÎÏÊ ÉÚ ÔÉÐÉÞÎÙÈ ÓÈÅÍ Ñ×ÌÑÅÔÓÑ ÓÈÅÍÁ é-îå, ÏÎÁ ÉÍÅÅÔ Ä×Á ×ÈÏÄÁ É

ÏÄÉÎ ×ÙÈÏÄ. óÉÇÎÁÌ ÎÁ ×ÙÈÏÄÅ Ñ×ÌÑÅÔÓÑ ÏÔÒÉÃÁÎÉÅÍ ËÏÎßÀÎËÃÉÉ ÓÉÇÎÁÌÏ×

ÎÁ ×ÈÏÄÅ. äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÎÁ ×ÙÈÏÄÅ ÐÏÑ×ÌÑÅÔÓÑ ×ÙÓÏËÉÊ ÐÏÔÅÎÃÉÁÌ (ÓÉÇ-

ÎÁÌ 1) ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÎÁ ÏÄÎÏÍ ÉÚ ×ÈÏÄÏ× ÐÏÔÅÎÃÉÁÌ ÎÉÚËÉÊ (0).

éÚ ÔÁËÏÊ ÓÈÅÍÙ ÌÅÇËÏ ÐÏÌÕÞÉÔØ ÓÈÅÍÕ îå (ÉÚÍÅÎÑÀÝÕÀ ÕÒÏ×ÅÎØ ÓÉÇÎÁÌÁ

ÎÁ ÐÒÏÔÉ×ÏÐÏÌÏÖÎÙÊ), ÓÏÅÄÉÎÉ× ÐÒÏ×ÏÄÏÍ Ä×Á ×ÈÏÄÁ. ðÒÉ ÜÔÏÍ ÎÁ ÏÂÁ ×ÈÏÄÁ

ÐÏÓÔÕÐÁÅÔ ÏÄÉÎ É ÔÏÔ ÖÅ ÓÉÇÎÁÌ, É ÏÐÅÒÁÃÉÑ é ÅÇÏ ÎÅ ÍÅÎÑÅÔ (p∧p = p), Á îå

ÍÅÎÑÅÔ ÎÁ ÐÒÏÔÉ×ÏÐÏÌÏÖÎÙÊ. ÷ÚÑ× Ä×Á ÜÌÅÍÅÎÔÁ é-îå É ÉÓÐÏÌØÚÕÑ ×ÔÏÒÏÊ

ÉÚ ÎÉÈ × ËÁÞÅÓÔ×Å ÜÌÅÍÅÎÔÁ îå, ÉÎ×ÅÒÔÉÒÕÀÝÅÇÏ ÓÉÇÎÁÌ Ó ×ÙÈÏÄÁ ÐÅÒ×ÏÇÏ

ÜÌÅÍÅÎÔÁ, ÐÏÌÕÞÁÅÍ ÓÈÅÍÕ, ËÏÔÏÒÁÑ ÒÅÁÌÉÚÕÅÔ ÆÕÎËÃÉÀ é. á ÅÓÌÉ ÐÏÓÔÁ×ÉÔØ

Ä×Á ÜÌÅÍÅÎÔÁ îå ÐÅÒÅÄ ËÁÖÄÙÍ ÉÚ ×ÈÏÄÏ× ÜÌÅÍÅÎÔÁ é-îå, ÐÏÌÕÞÉÍ ÓÈÅÍÕ,

ÒÅÁÌÉÚÕÀÝÕÀ ÆÕÎËÃÉÀ éìé: ¬(¬p ∧ ¬q) ↔ (p ∨ q).

ôÅÏÒÅÍÁ 19 Ï ÐÏÌÎÏÔÅ ÓÉÓÔÅÍÙ Ó×ÑÚÏË ÔÅÐÅÒØ ÇÁÒÁÎÔÉÒÕÅÔ, ÞÔÏ ÌÀÂÕÀ

ÂÕÌÅ×Õ ÆÕÎËÃÉÀ ÍÏÖÎÏ ÒÅÁÌÉÚÏ×ÁÔØ × ×ÉÄÅ ÓÈÅÍÙ. îÁÄÏ ÉÍÅÔØ × ×ÉÄÕ, ÏÄ-

ÎÁËÏ, ÞÔÏ ÐÒÅÄÌÁÇÁÅÍÁÑ × Å¾ ÄÏËÁÚÁÔÅÌØÓÔ×Å ËÏÎÓÔÒÕËÃÉÑ (ÄÉÚßÀÎËÔÉ×ÎÁÑ

ÎÏÒÍÁÌØÎÁÑ ÆÏÒÍÁ) ÉÍÅÅÔ ÓËÏÒÅÅ ÔÅÏÒÅÔÉÞÅÓËÉÊ ÉÎÔÅÒÅÓ, ÐÏÓËÏÌØËÕ ÐÒÉ×Ï-

ÄÉÔ Ë ÓÈÅÍÁÍ ÏÞÅÎØ ÂÏÌØÛÏÇÏ ÒÁÚÍÅÒÁ ÄÁÖÅ ÄÌÑ ÐÒÏÓÔÙÈ ÆÕÎËÃÉÊ (ÅÓÌÉ

ÞÉÓÌÏ ÁÒÇÕÍÅÎÔÏ× ×ÅÌÉËÏ). îÁÐÒÉÍÅÒ, ÓÈÅÍÁ, ÓÒÁ×ÎÉ×ÁÀÝÁÑ Ä×Á 16-ÂÉÔÎÙÈ

ÞÉÓÌÁ, ÄÏÌÖÎÁ ÉÍÅÔØ 32 ×ÈÏÄÁ É ÐÏÜÔÏÍÕ × Å¾ ÒÅÁÌÉÚÁÃÉÉ Ó ÐÏÍÏÝØÀ ÄÉÚß-

ÀÎËÔÉ×ÎÏÊ ÎÏÒÍÁÌØÎÏÊ ÆÏÒÍÙ ÂÕÄÅÔ ÐÏÒÑÄËÁ 2

ÜÌÅÍÅÎÔÏ× ¡ ÞÔÏ ÍÁÌÏ

ÒÅÁÌØÎÏ. (íÅÖÄÕ ÔÅÍ ÔÁËÕÀ ÓÈÅÍÕ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÇÏÒÁÚÄÏ ÐÒÏÝÅ, ÉÚ ÎÅ-

ÓËÏÌØËÉÈ ÓÏÔÅÎ ÜÌÅÍÅÎÔÏ×.)

ðÏÜÔÏÍÕ ×ÏÐÒÏÓ Ï ÔÏÍ, ÓËÏÌØËÏ ÜÌÅÍÅÎÔÏ× ÎÕÖÎÏ ÄÌÑ ÒÅÁÌÉÚÁÃÉÉ ÔÏÊ ÉÌÉ

ÉÎÏÊ ÆÕÎËÃÉÉ, ÐÒÅÄÓÔÁ×ÌÑÅÔ ÂÏÌØÛÏÊ ÉÎÔÅÒÅÓ ¡ ËÁË ÐÒÁËÔÉÞÅÓËÉÊ, ÔÁË É

ÆÉÌÏÓÏÆÓËÉÊ. (ïÄÎÁ ÉÚ ÃÅÎÔÒÁÌØÎÙÈ ÐÒÏÂÌÅÍ ÍÁÔÅÍÁÔÉËÉ É ÉÎÆÏÒÍÁÔÉËÉ,

ÔÁË ÎÁÚÙ×ÁÅÍÁÑ ¥ÐÒÏÂÌÅÍÁ ÐÅÒÅÂÏÒÁ¥, ÍÏÖÅÔ ÂÙÔØ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÁ × ÜÔÉÈ

ÔÅÒÍÉÎÁÈ.)

íÙ ÓÅÊÞÁÓ ÄÁÄÉÍ ÂÏÌÅÅ ÆÏÒÍÁÌØÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÓÈÅÍÙ É ÒÅÁÌÉÚÕÅÍÏÊ

ÅÊ ÂÕÌÅ×ÏÊ ÆÕÎËÃÉÉ. îÏ ÐÒÅÖÄÅ ×ÓÅÇÏ ÏÔ×ÅÔÉÍ ÎÁ ÔÁËÏÊ ×ÏÐÒÏÓ ¡ ÐÏÞÅÍÕ

ÍÙ ×ÏÏÂÝÅ ÇÏ×ÏÒÉÍ Ï ÓÈÅÍÁÈ? ÷ÅÄØ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ËÏÍÐÏÚÉÃÉÀ ÂÕÌÅ×ÙÈ

ÆÕÎËÃÉÊ × ×ÉÄÅ ÆÏÒÍÕÌÙ, ÎÅ ÂÕÄÅÔ ÌÉ ÜÔÏ ÔÏ ÖÅ ÓÁÍÏÅ?

ïËÁÚÙ×ÁÅÔÓÑ, ÎÅ ÓÏ×ÓÅÍ, É ÒÁÚÎÉÃÕ ÌÅÇËÏ Õ×ÉÄÅÔØ ÎÁ ÐÒÉÍÅÒÅ (ÒÉÓ. 2).

h h(g

(f(x)), g

(f(x)))

òÉÓ. 2. üÌÅÍÅÎÔ ×ÈÏÄÉÔ × ÆÏÒÍÕÌÕ Ä×ÁÖÄÙ.

úÄÅÓØ ÏÄÉÎ É ÔÏÔ ÖÅ ÜÌÅÍÅÎÔ ÓÈÅÍÙ (f) ÐÒÉÈÏÄÉÔÓÑ ÕËÁÚÙ×ÁÔØ × ÆÏÒÍÕÌÅ

72 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

Ä×ÁÖÄÙ, ÐÏÓËÏÌØËÕ ÅÇÏ ×ÙÈÏÄ ÉÓÐÏÌØÚÕÅÔÓÑ × ËÁÞÅÓÔ×Å ×ÈÏÄÁ Ä×ÕÈ ÄÒÕÇÉÈ

ÜÌÅÍÅÎÔÏ×. óÈÅÍÙ, × ËÏÔÏÒÙÈ ÔÁËÏÇÏ ×ÅÔ×ÌÅÎÉÑ ÎÅÔ (ÎÁ ÐÒÁËÔÉËÅ ×ÅÔ×ÌÅÎÉÅ

×ÐÏÌÎÅ ×ÏÚÍÏÖÎÏ, ÈÏÔÑ É ÏÇÒÁÎÉÞÅÎÏ ¥ÎÁÇÒÕÚÏÞÎÏÊ ÓÐÏÓÏÂÎÏÓÔØÀ ×ÙÈÏÄÁ¥,

ËÁË ÇÏ×ÏÒÑÔ ÉÎÖÅÎÅÒÙ), ËÁË ÒÁÚ É ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ ÆÏÒÍÕÌÁÍ. îÏ × ÏÂÝÅÍ

ÓÌÕÞÁÅ ÐÏÌÕÞÅÎÎÁÑ ÉÚ ÄÁÎÎÏÊ ÓÈÅÍÙ ÆÏÒÍÕÌÁ ÍÏÖÅÔ ÂÙÔØ ÄÌÉÎÎÏÊ, ÄÁÖÅ

ÅÓÌÉ ÓÈÅÍÁ ÓÏÄÅÒÖÉÔ ÎÅÂÏÌØÛÏÅ ÞÉÓÌÏ ÜÌÅÍÅÎÔÏ×, ÐÏÓËÏÌØËÕ ÞÉÓÌÏ ËÏÐÉÊ

ÍÏÖÅÔ ÒÁÓÔÉ ÜËÓÐÏÎÅÎÃÉÁÌØÎÏ Ó ÒÏÓÔÏÍ ÇÌÕÂÉÎÙ ÓÈÅÍÙ.

èÏÔÑ ÉÄÅÑ ÏÂÒÁÚÏ×ÁÎÉÑ ÓÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ×, ÒÅÁÌÉÚÕÀ-

ÝÉÈ ÂÕÌÅ×Ù ÆÕÎËÃÉÉ, ÄÏÓÔÁÔÏÞÎÏ ÎÁÇÌÑÄÎÁ, ÄÁÄÉÍ ÂÏÌÅÅ ÆÏÒÍÁÌØÎÏÅ ÏÐÒÅ-

ÄÅÌÅÎÉÅ. æÉËÓÉÒÕÅÍ ÎÅËÏÔÏÒÙÊ ÎÁÂÏÒ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ B. ðÕÓÔØ ÉÍÅÅÔÓÑ

n ÂÕÌÅ×ÙÈ (ÐÒÉÎÉÍÁÀÝÉÈ ÚÎÁÞÅÎÉÑ 0 É 1) ÐÅÒÅÍÅÎÎÙÈ x

, . . . , x

, ÎÁÚÙ×ÁÅ-

ÍÙÈ ×ÈÏÄÁÍÉ. ðÕÓÔØ ÔÁËÖÅ ÉÍÅÅÔÓÑ ÎÅËÏÔÏÒÏÅ ÞÉÓÌÏ ÂÕÌÅ×ÙÈ ÐÅÒÅÍÅÎÎÙÈ

, . . . , y

, ÎÁÚÙ×ÁÅÍÙÈ ÐÒÏ×ÏÄÎÉËÁÍÉ. ðÕÓÔØ ÄÌÑ ËÁÖÄÏÇÏ ÐÒÏ×ÏÄÎÉËÁ ÓÈÅ-

ÍÙ ÚÁÄÁÎÁ ÂÕÌÅ×Á ÆÕÎËÃÉÑ ÉÚ B, ×ÙÒÁÖÁÀÝÁÑ ÅÇÏ ÚÎÁÞÅÎÉÅ ÞÅÒÅÚ ÄÒÕÇÉÅ

ÐÒÏ×ÏÄÎÉËÉ É ×ÈÏÄÙ. ðÒÉ ÜÔÏÍ ÔÒÅÂÕÅÔÓÑ, ÞÔÏÂÙ ÎÅ ÂÙÌÏ ÃÉËÌÏ× (ÃÉËÌ ÏÂÒÁ-

ÚÕÅÔÓÑ, ËÏÇÄÁ y

ÚÁ×ÉÓÉÔ ÏÔ y

, ËÏÔÏÒÏÅ ÚÁ×ÉÓÉÔ ÏÔ y

, . . . , ËÏÔÏÒÏÅ ÚÁ×ÉÓÉÔ

ÏÔ y

). ðÕÓÔØ, ËÒÏÍÅ ÔÏÇÏ, ÓÒÅÄÉ ÐÒÏ×ÏÄÎÉËÏ× ×ÙÄÅÌÅÎ ÏÄÉÎ, ÎÁÚÙ×ÁÅÍÙÊ

×ÙÈÏÄÏÍ. ÷ ÔÁËÏÍ ÓÌÕÞÁÅ ÇÏ×ÏÒÑÔ, ÞÔÏ ÚÁÄÁÎÁ ÓÈÅÍÁ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ

ÜÌÅÍÅÎÔÏ× × ÂÁÚÉÓÅ B Ó n ×ÈÏÄÁÍÉ. þÉÓÌÏ m ÎÁÚÙ×ÁÀÔ ÒÁÚÍÅÒÏÍ ÓÈÅÍÙ. (ó

ÔÏÞËÉ ÚÒÅÎÉÑ ÉÎÖÅÎÅÒÁ ÒÁÚÍÅÒ ¡ ÜÔÏ ÞÉÓÌÏ ÉÓÐÏÌØÚÏ×ÁÎÎÙÈ ÜÌÅÍÅÎÔÏ×, Á

ÂÁÚÉÓ B ¡ ÜÔÏ ÁÓÓÏÒÔÉÍÅÎÔ ÄÏÓÔÕÐÎÙÈ ÅÍÕ ÜÌÅÍÅÎÔÏ×.)

ïÔÓÕÔÓÔ×ÉÅ ÃÉËÌÏ× ÇÁÒÁÎÔÉÒÕÅÔ, ÞÔÏ ÅÓÔØ ÐÒÏ×ÏÄÎÉË, ÚÁ×ÉÓÑÝÉÊ ÔÏÌØËÏ

ÏÔ ×ÈÏÄÏ× (ÉÎÁÞÅ ÍÏÖÎÏ ÂÙÌÏ ÂÙ ÎÁÊÔÉ ÃÉËÌ: ×ÏÚØÍ¾Í ËÁËÏÊ-ÔÏ ÐÒÏ×ÏÄÎÉË,

ÚÁÔÅÍ ×ÏÚØÍ¾Í ÔÏÔ ÐÒÏ×ÏÄÎÉË, ÏÔ ËÏÔÏÒÏÇÏ ÏÎ ÚÁ×ÉÓÉÔ É Ô. Ä.). úÎÁÞÅÎÉÅ

ÜÔÏÇÏ ÐÒÏ×ÏÄÎÉËÁ, ÔÁËÉÍ ÏÂÒÁÚÏÍ, ÏÄÎÏÚÎÁÞÎÏ ÏÐÒÅÄÅÌÑÅÔÓÑ ÓÉÇÎÁÌÁÍÉ ÎÁ

×ÈÏÄÁÈ. óÒÅÄÉ ÏÓÔÁ×ÛÉÈÓÑ ÐÒÏ×ÏÄÎÉËÏ× ÔÁËÖÅ ÎÅÔ ÃÉËÌÁ, ÐÏÜÔÏÍÕ ÍÏÖÎÏ

ÎÁÊÔÉ ÏÄÉÎ ÉÚ ÎÉÈ, ÚÁ×ÉÓÑÝÉÊ ÔÏÌØËÏ ÏÔ ÕÖÅ ÉÚ×ÅÓÔÎÙÈ, É ÏÐÒÅÄÅÌÉÔØ ÅÇÏ

ÚÎÁÞÅÎÉÅ. ðÅÒÅÎÕÍÅÒÏ×Á× ÐÒÏ×ÏÄÎÉËÉ × ÔÁËÏÍ ÐÏÒÑÄËÅ, ÍÙ ÍÏÖÅÍ ÚÁÐÉÓÁÔØ

ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÐÒÉÓ×ÁÉ×ÁÎÉÊ

:= f

(. . . );

:= f

(. . . );

. . . . . . . .

:= f

(. . . ),

× ÐÒÁ×ÙÈ ÞÁÓÔÑÈ ËÏÔÏÒÙÈ ÓÔÏÑÔ ÆÕÎËÃÉÉ ÉÚ B, ÐÒÉÍÅÎ¾ÎÎÙÅ ËÏ ×ÈÏÄÁÍ É

ÕÖÅ ÎÁÊÄÅÎÎÙÍ ÚÎÁÞÅÎÉÑÍ. ðÒÉ ÜÔÏÍ ÍÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÒÅÚÕÌØÔÁÔ ÓÈÅÍÙ

ÅÓÔØ y

(×ÓÅ ÐÏÓÌÅÄÕÀÝÉÅ ÐÒÉÓ×ÁÉ×ÁÎÉÑ ÕÖÅ ÎÅ ÎÕÖÎÙ). ôÁËÁÑ ÐÒÏÇÒÁÍÍÁ

ÏÐÒÅÄÅÌÑÅÔ y

ÐÒÉ ÉÚ×ÅÓÔÎÙÈ ÚÎÁÞÅÎÉÑÈ ×ÈÏÄÏ×, É ÔÅÍ ÓÁÍÙÍ ×ÙÞÉÓÌÑÅÔ

ÎÅËÏÔÏÒÕÀ ÂÕÌÅ×Õ ÆÕÎËÃÉÀ.

§3. óÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ× 73

ôÅÐÅÒØ ÎÁÂÏÒ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ B ÍÏÖÎÏ ÎÁÚ×ÁÔØ ÐÏÌÎÙÍ, ÅÓÌÉ ÌÀÂÁÑ ÂÕ-

ÌÅ×Á ÆÕÎËÃÉÑ ÍÏÖÅÔ ÂÙÔØ ÚÁÄÁÎÁ ÓÈÅÍÏÊ ÉÚ B-ÜÌÅÍÅÎÔÏ× (ÓÕÝÅÓÔ×ÕÅÔ ÐÒÏ-

ÇÒÁÍÍÁ, Å¾ ×ÙÞÉÓÌÑÀÝÁÑ, ÐÒÉ ÜÔÏÍ × ÐÒÁ×ÙÈ ÞÁÓÔÑÈ ÐÒÉÓ×ÁÉ×ÁÎÉÊ ÓÔÏÑÔ

ÆÕÎËÃÉÉ ÉÚ B). ñÓÎÏ, ÞÔÏ ÜÔÏ ÏÐÒÅÄÅÌÅÎÉÅ ÐÏÌÎÏÔÙ ÒÁ×ÎÏÓÉÌØÎÏ ÐÒÅÖÎÅÍÕ,

ÔÏ ÅÓÔØ ×ÏÚÍÏÖÎÏÓÔÉ ÚÁÐÉÓÁÔØ ÂÕÌÅ×Õ ÆÕÎËÃÉÀ × ×ÉÄÅ ÆÏÒÍÕÌÙ ÓÏ Ó×ÑÚËÁÍÉ

ÉÚ B (ËÁË ÍÙ ÇÏ×ÏÒÉÌÉ, ÒÁÚÎÉÃÁ ÔÏÌØËÏ × ÔÏÍ, ÞÔÏ ÏÄÉÎ É ÔÏÔ ÖÅ ÜÌÅÍÅÎÔ

ÂÕÄÅÔ ÆÉÇÕÒÉÒÏ×ÁÔØ × ÆÏÒÍÕÌÅ ÍÎÏÇÏËÒÁÔÎÏ).

óÌÏÖÎÏÓÔØÀ ÂÕÌÅ×ÏÊ ÆÕÎËÃÉÉ f ÏÔÎÏÓÉÔÅÌØÎÏ B ÎÁÚÙ×ÁÀÔ ÍÉÎÉÍÁÌØ-

ÎÙÊ ÒÁÚÍÅÒ ÓÈÅÍÙ ÉÚ B-ÜÌÅÍÅÎÔÏ×, ×ÙÞÉÓÌÑÀÝÅÊ ÆÕÎËÃÉÀ f. åÇÏ ÏÂÏÚÎÁ-

ÞÁÀÔ size

(f).

ôÅÏÒÅÍÁ 23. ðÕÓÔØ B

É B

¡ Ä×Á ÐÏÌÎÙÈ ÎÁÂÏÒÁ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ.

ôÏÇÄÁ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÅ ÍÅÒÙ ÓÌÏÖÎÏÓÔÉ ÏÔÌÉÞÁÀÔÓÑ ÎÅ ÂÏÌÅÅ ÞÅÍ

ÎÁ ÐÏÓÔÏÑÎÎÙÊ ÍÎÏÖÉÔÅÌØ: ÎÁÊÄ¾ÔÓÑ ÔÁËÏÅ ÞÉÓÌÏ C, ÞÔÏ size

(f) 6

6 C size

(f) É size

(f) 6 C size

(f) ÄÌÑ ÌÀÂÏÊ ÆÕÎËÃÉÉ f.

äÏËÁÚÁÔÅÌØÓÔ×Ï. õÔ×ÅÒÖÄÅÎÉÅ ÐÏÞÔÉ ÏÞÅ×ÉÄÎÏ: ÐÏÓËÏÌØËÕ ÎÁÂÏÒÙ B

ÐÏÌÎÙ, ÔÏ ËÁÖÄÁÑ ÆÕÎËÃÉÑ ÏÄÎÏÇÏ ÉÚ ÎÁÂÏÒÏ× ÍÏÖÅÔ ÂÙÔØ ×ÙÞÉÓÌÅÎÁ

ËÁËÏÊ-ÔÏ ÓÈÅÍÏÊ, ÓÏÓÔÁ×ÌÅÎÎÏÊ ÉÚ ÜÌÅÍÅÎÔÏ× ÄÒÕÇÏÇÏ ÎÁÂÏÒÁ. ôÅÐÅÒØ ÍÏÖÎÏ

×ÚÑÔØ × ËÁÞÅÓÔ×Å C ÎÁÉÂÏÌØÛÉÊ ÒÁÚÍÅÒ ÔÁËÉÈ ÓÈÅÍ, É ÎÅÒÁ×ÅÎÓÔ×Á ÂÕÄÕÔ ×Ù-

ÐÏÌÎÑÔØÓÑ: ËÁÖÄÕÀ ÓÔÒÏËÕ ÐÒÏÇÒÁÍÍÙ ÍÏÖÎÏ ÚÁÍÅÎÉÔØ ÎÁ C (ÉÌÉ ÍÅÎØÛÅ)

ÓÔÒÏË Ó ÉÓÐÏÌØÚÏ×ÁÎÉÅÍ ÆÕÎËÃÉÊ ÄÒÕÇÏÇÏ ÎÁÂÏÒÁ.

þÔÏ ÍÏÖÎÏ ÓËÁÚÁÔØ Ï ÓÌÏÖÎÏÓÔÉ ÐÒÏÉÚ×ÏÌØÎÏÊ ÂÕÌÅ×ÏÊ ÆÕÎËÃÉÉ n ÁÒÇÕ-

ÍÅÎÔÏ×? óÌÅÄÕÀÝÁÑ ÔÅÏÒÅÍÁ ÐÏËÁÚÙ×ÁÅÔ, ÞÔÏ ÏÎÁ ÜËÓÐÏÎÅÎÃÉÁÌØÎÏ ÚÁ×ÉÓÉÔ

ÏÔ n (ÄÌÑ ¥ÎÁÕÇÁÄ ×ÚÑÔÏÊ¥ ÆÕÎËÃÉÉ).

ôÅÏÒÅÍÁ 24. ( Á) ðÕÓÔØ c > 2. ôÏÇÄÁ ÓÌÏÖÎÏÓÔØ ÌÀÂÏÊ ÂÕÌÅ×ÏÊ ÆÕÎË-

ÃÉÉ n ÁÒÇÕÍÅÎÔÏ× ÎÅ ÐÒÅ×ÏÓÈÏÄÉÔ c

ÄÌÑ ×ÓÅÈ ÄÏÓÔÁÔÏÞÎÏ ÂÏÌØÛÉÈ n.

( Â) ðÕÓÔØ c < 2. ôÏÇÄÁ ÓÌÏÖÎÏÓÔØ ÂÏÌØÛÉÎÓÔ×Á ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ n ÁÒÇÕ-

ÍÅÎÔÏ× ÎÅ ÍÅÎØÛÅ c

ÄÌÑ ×ÓÅÈ ÄÏÓÔÁÔÏÞÎÏ ÂÏÌØÛÉÈ n.

äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÒÅÖÄÅ ×ÓÅÇÏ ÚÁÍÅÔÉÍ, ÞÔÏ ÐÏ ÐÒÅÄÙÄÕÝÅÊ ÔÅÏÒÅÍÅ ÎÅ

ÉÍÅÅÔ ÚÎÁÞÅÎÉÑ, ËÁËÏÊ ÐÏÌÎÙÊ ÂÁÚÉÓ ×ÙÂÒÁÔØ (ÉÚÍÅÎÅÎÉÅ ÚÎÁÞÅÎÉÑ c ÂÏÌÅÅ

ÓÕÝÅÓÔ×ÅÎÎÏ, ÞÅÍ ÕÍÎÏÖÅÎÉÅ ÓÌÏÖÎÏÓÔÉ ÎÁ ËÏÎÓÔÁÎÔÕ).

ðÅÒ×ÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÔÅÏÒÅÍÙ ÏÞÅ×ÉÄÎÏ: ÒÁÚÍÅÒ ÓÈÅÍÙ, ÒÅÁÌÉÚÕÀÝÅÊ

ÄÉÚßÀÎËÔÉ×ÎÕÀ ÎÏÒÍÁÌØÎÕÀ ÆÏÒÍÕ Ó n ÐÅÒÅÍÅÎÎÙÍÉ, ÅÓÔØ O(n2

), ÐÏ-

ÓËÏÌØËÕ ÉÍÅÅÔÓÑ ÎÅ ÂÏÌÅÅ 2

ËÏÎßÀÎËÔÏ× ÒÁÚÍÅÒÁ O(n). (îÁÐÏÍÎÉÍ ÓÍÙÓÌ

O-ÏÂÏÚÎÁÞÅÎÉÊ: O(n2

) ÏÚÎÁÞÁÅÔ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ ×ÅÒÈÎÑÑ ÏÃÅÎËÁ ×ÉÄÁ Cn2

ÄÌÑ ÎÅËÏÔÏÒÏÊ ËÏÎÓÔÁÎÔÙ C.) ïÓÔÁÌÏÓØ ÚÁÍÅÔÉÔØ, ÞÔÏ O(n2

) < c

ÐÒÉ ÄÏ-

ÓÔÁÔÏÞÎÏ ÂÏÌØÛÉÈ n (ÎÁÐÏÍÎÉÍ, ÞÔÏ c > 2).

þÔÏÂÙ ÄÏËÁÚÁÔØ ×ÔÏÒÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ, ÏÃÅÎÉÍ ÞÉÓÌÏ ÒÁÚÌÉÞÎÙÈ ÓÈÅÍ (ÓËÁ-

ÖÅÍ, × ÂÁÚÉÓÅ é, éìé, îå) ÒÁÚÍÅÒÁ N Ó n ÁÒÇÕÍÅÎÔÁÍÉ. ëÁÖÄÁÑ ÔÁËÁÑ

74 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

ÓÈÅÍÁ ÍÏÖÅÔ ÂÙÔØ ÏÐÉÓÁÎÁ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØÀ ÉÚ N ÐÒÉÓ×ÁÉ×ÁÎÉÊ, ×ÙÒÁ-

ÖÁÀÝÉÈ ÏÄÎÕ ÉÚ ÐÅÒÅÍÅÎÎÙÈ ÞÅÒÅÚ ÐÒÅÄÙÄÕÝÉÅ. äÌÑ ËÁÖÄÏÇÏ ÐÒÉÓ×ÁÉ×Á-

ÎÉÑ ÅÓÔØ ÎÅ ÂÏÌÅÅ 3(N + n)

×ÁÒÉÁÎÔÏ× (ÔÒÉ ÔÉÐÁ ÏÐÅÒÁÃÉÊ ¡ ËÏÎßÀÎËÃÉÑ,

ÄÉÚßÀÎËÃÉÑ, ÏÔÒÉÃÁÎÉÅ, É ËÁÖÄÙÊ ÉÚ ÎÅ ÂÏÌÅÅ ÞÅÍ Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ× ×ÙÂÉ-

ÒÁÅÔÓÑ ÓÒÅÄÉ ÎÅ ÂÏÌÅÅ ÞÅÍ N +n ×ÁÒÉÁÎÔÏ×). ïÔÓÀÄÁ ÌÅÇËÏ ÐÏÌÕÞÉÔØ ÏÃÅÎËÕ

O(N log N )

ÎÁ ÞÉÓÌÏ ×ÓÅÈ ÆÕÎËÃÉÊ ÓÌÏÖÎÏÓÔÉ ÎÅ ÂÏÌÅÅ N (ÓÞÉÔÁÑ N > n).

÷ÓÅÇÏ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ Ó n ÁÒÇÕÍÅÎÔÁÍÉ ÉÍÅÅÔÓÑ 2

. éÚ ÓÒÁ×ÎÅÎÉÑ ÜÔÉÈ

ÆÏÒÍÕÌ ×ÉÄÎÏ, ÞÔÏ ÞÔÏ ÐÒÉ c < 2 É ÐÒÉ ÄÏÓÔÁÔÏÞÎÏ ÂÏÌØÛÉÈ n ÂÕÌÅ×Ù

ÆÕÎËÃÉÉ ÓÌÏÖÎÏÓÔÉ ÍÅÎØÛÅ c

ÓÏÓÔÁ×ÌÑÀÔ ÍÅÎØÛÉÎÓÔ×Ï, ÔÁË ËÁË 2

O(c

log c

)

ÍÎÏÇÏ ÍÅÎØÛÅ 2

úÁÄÁÞÁ 113. ðÒÏ×ÅÄÉÔÅ ×ÔÏÒÕÀ ÞÁÓÔØ ÒÁÓÓÕÖÄÅÎÉÑ ÂÏÌÅÅ ÐÏÄÒÏÂÎÏ É

ÐÏËÁÖÉÔÅ, ÞÔÏ ÐÒÉ ÎÅËÏÔÏÒÏÍ ε > 0 ÓÌÏÖÎÏÓÔØ ÂÏÌØÛÉÎÓÔ×Á ÂÕÌÅ×ÙÈ

ÆÕÎËÃÉÊ Ó n ÁÒÇÕÍÅÎÔÁÍÉ ÎÅ ÍÅÎØÛÅ ε2

/n.

÷ÅÒÈÎÀÀ ÏÃÅÎËÕ × ÔÅÏÒÅÍÅ 24 ÍÏÖÎÏ ÕÓÉÌÉÔØ É ÐÏËÁÚÁÔØ, ÞÔÏ ÓÌÏÖÎÏÓÔØ

ÌÀÂÏÊ ÂÕÌÅ×ÏÊ ÆÕÎËÃÉÉ n ÁÒÇÕÍÅÎÔÏ× ÎÅ ÐÒÅ×ÏÓÈÏÄÉÔ O(2

/n).

úÁÄÁÞÁ 114. ( Á) ðÏËÁÖÉÔÅ, ÞÔÏ ×ÏÚÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÓÈÅÍÕ ÒÁÚÍÅ-

ÒÁ O(2

) Ó 2

×ÙÈÏÄÁÍÉ, ÒÅÁÌÉÚÕÀÝÕÀ ×ÓÅ 2

×ÏÚÍÏÖÎÙÈ ËÏÎßÀÎËÔÏ×

ÄÌÉÎÙ m (ÄÌÑ ËÁÖÄÏÇÏ ¡ Ó×ÏÊ ×ÙÈÏÄ). (õËÁÚÁÎÉÅ: ÔÁËÕÀ ÓÈÅÍÕ ÍÏÖÎÏ

ÐÏÓÔÒÏÉÔØ ÉÎÄÕËÔÉ×ÎÏ.) ( Â) ðÏËÁÖÉÔÅ, ÞÔÏ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÓÈÅÍÕ

ÒÁÚÍÅÒÁ O(2

) Ó 2

×ÙÈÏÄÁÍÉ, ÒÅÁÌÉÚÕÀÝÕÀ ×ÓÅ 2

ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ m

ÁÒÇÕÍÅÎÔÏ×. (õËÁÚÁÎÉÅ: ÜÔÕ ÓÈÅÍÕ ÔÁËÖÅ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÉÎÄÕËÔÉ×-

ÎÏ.) ( ×) ðÕÓÔØ ϕ(x

, . . . , x

, y

, . . . , y

) ¡ ÂÕÌÅ×Á ÆÕÎËÃÉÑ, ÁÒÇÕÍÅÎÔÙ ËÏ-

ÔÏÒÏÊ ÒÁÚÂÉÔÙ ÎÁ Ä×Å ÇÒÕÐÐÙ. ðÏËÁÖÉÔÅ, ÞÔÏ Å¾ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ × ×É-

ÄÅ ÄÉÚßÀÎËÃÉÉ 2

ÞÌÅÎÏ×, ËÁÖÄÙÊ ÉÚ ËÏÔÏÒÙÈ ÉÍÅÅÔ ×ÉÄ C(x

, . . . , x

) ∧

∧ D(y

, . . . , y

), ÇÄÅ C ¡ ËÏÎßÀÎËÔ, Á D ¡ ÐÒÏÉÚ×ÏÌØÎÁÑ ÂÕÌÅ×Á ÆÕÎËÃÉÑ.

÷Ù×ÅÓÔÉ ÏÔÓÀÄÁ ÕÐÏÍÑÎÕÔÕÀ ×ÙÛÅ ÏÃÅÎËÕ O(2

/n). (õËÁÚÁÎÉÅ: ÒÁÚÕÍÎÏ

ÐÏÌÏÖÉÔØ k = n − log n + c, l = log n − c.)

ôÅÏÒÅÍÁ 24, ÏÄÎÁËÏ, ÎÉÞÅÇÏ ÎÅ ÇÏ×ÏÒÉÔ Ï ÓÌÏÖÎÏÓÔÉ ËÏÎËÒÅÔÎÙÈ ÂÕÌÅ×ÙÈ

ÆÕÎËÃÉÊ. óÉÔÕÁÃÉÑ ÚÄÅÓØ ÔÁËÏ×Á. åÓÔØ ÒÁÚÎÏÏÂÒÁÚÎÙÅ ÍÅÔÏÄÙ É ÐÒÉ¾ÍÙ

ÐÏÌÕÞÅÎÉÑ ×ÅÒÈÎÉÈ ÏÃÅÎÏË. îÏ ÐÒÏ ÎÉÖÎÉÅ ÏÃÅÎËÉ ÎÅÉÚ×ÅÓÔÎÏ ÐÒÁËÔÉÞÅ-

ÓËÉ ÎÉÞÅÇÏ. ðÒÏ ÍÎÏÇÉÅ ÆÕÎËÃÉÉ ÍÙ ÐÏÄÏÚÒÅ×ÁÅÍ, ÞÔÏ ÉÈ ÓÌÏÖÎÏÓÔØ ×ÅÌÉËÁ

(ÜËÓÐÏÎÅÎÃÉÁÌØÎÏ ÚÁ×ÉÓÉÔ ÏÔ ÞÉÓÌÁ ×ÈÏÄÏ×), ÎÏ ÄÏËÁÚÁÔØ ÜÔÏ ÐÏËÁ ÎÅ ÕÄÁ¾Ô-

ÓÑ. ÷ÅÓØÍÁ ÎÅÔÒÉ×ÉÁÌØÎÙÅ ÉÄÅÉ ÐÏÚ×ÏÌÑÀÔ ÄÏËÁÚÙ×ÁÔØ ÜËÓÐÏÎÅÎÃÉÁÌØÎÙÅ

ÎÉÖÎÉÅ ÏÃÅÎËÉ ÄÌÑ ÎÅËÏÔÏÒÙÈ ÓÐÅÃÉÁÌØÎÙÈ ËÌÁÓÓÏ× ÓÈÅÍ, ÎÁÐÒÉÍÅÒ, ÓÈÅÍ

ÉÚ ÍÏÎÏÔÏÎÎÙÈ ÜÌÅÍÅÎÔÏ× ÉÌÉ ÓÈÅÍ ÏÇÒÁÎÉÞÅÎÎÏÊ ÇÌÕÂÉÎÙ (ÉÓÐÏÌØÚÕÀÝÉÈ

ÜÌÅÍÅÎÔÙ é É éìé Ó ÐÒÏÉÚ×ÏÌØÎÙÍ ÞÉÓÌÏÍ ×ÈÏÄÏ×). ðÏÌÕÞÅÎÉÅ ÜËÓÐÏÎÅÎ-

ÃÉÁÌØÎÙÈ ÏÃÅÎÏË ÄÌÑ ÂÏÌÅÅ ÏÂÝÉÈ ÓÈÅÍ ¡ ÏÄÉÎ ÉÚ ×ÏÚÍÏÖÎÙÈ ÐÏÄÈÏÄÏ× Ë

§3. óÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ× 75

ÚÎÁÍÅÎÉÔÏÊ ÐÒÏÂÌÅÍÅ ÐÅÒÅÂÏÒÁ, ÃÅÎÔÒÁÌØÎÏÊ ÐÒÏÂÌÅÍÅ ÔÅÏÒÉÉ ÓÌÏÖÎÏÓÔÉ

×ÙÞÉÓÌÅÎÉÊ.

íÙ ÎÅ ÂÕÄÅÍ ÕÇÌÕÂÌÑÔØÓÑ × ÜÔÕ ÔÅÏÒÉÀ, Á ÐÒÉ×ÅÄ¾Í ÌÉÛØ ÎÅÓËÏÌØËÏ ×ÅÒÈ-

ÎÉÈ ÏÃÅÎÏË ÄÌÑ ËÏÎËÒÅÔÎÙÈ ÚÁÄÁÞ. ðÒÉ ÜÔÏÍ ÍÙ ÎÅ ÐÒÅÔÅÎÄÕÅÍ ÎÁ ÐÏÌÎÏÔÕ,

Á ÈÏÔÉÍ ÌÉÛØ ÐÏËÁÚÁÔØ ÎÅÓËÏÌØËÏ ÉÎÔÅÒÅÓÎÙÈ ÉÄÅÊ É ÐÒÉ¾ÍÏ×.

òÁÓÓÍÏÔÒÉÍ ÆÕÎËÃÉÀ ÓÒÁ×ÎÅÎÉÑ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ. ïÎÁ ÉÍÅÅÔ 2n

ÁÒÇÕÍÅÎÔÏ× (n ÄÌÑ ÏÄÎÏÇÏ ÞÉÓÌÁ É n ÄÌÑ ÄÒÕÇÏÇÏ); Å¾ ÚÎÁÞÅÎÉÅ ÒÁ×ÎÏ 1, ÅÓÌÉ

ÐÅÒ×ÏÅ ÞÉÓÌÏ ÂÏÌØÛÅ ×ÔÏÒÏÇÏ, É 0 × ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ.

ïÂÏÚÎÁÞÉÍ ÜÔÕ ÆÕÎËÃÉÀ Comp

ôÅÏÒÅÍÁ 25. ðÕÓÔØ B ¡ ÐÏÌÎÙÊ ÎÁÂÏÒ ÆÕÎËÃÉÊ. óÕÝÅÓÔ×ÕÅÔ ÔÁËÁÑ

ËÏÎÓÔÁÎÔÁ C, ÞÔÏ size

(Comp

) 6 Cn.

äÏËÁÚÁÔÅÌØÓÔ×Ï. úÁÍÅÔÉÍ, ÞÔÏ ÐÏÓËÏÌØËÕ × ÆÏÒÍÕÌÉÒÏ×ËÅ ÔÅÏÒÅÍÙ ÏÃÅÎ-

ËÁ ÒÁÚÍÅÒÁ ÐÒÏ×ÏÄÉÔÓÑ Ó ÔÏÞÎÏÓÔØÀ ÄÏ ËÏÎÓÔÁÎÔÙ, ÔÏ ×ÙÂÏÒ ËÏÎËÒÅÔÎÏÇÏ

ÂÁÚÉÓÁ ÎÅ ÉÍÅÅÔ ÚÎÁÞÅÎÉÑ. äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÍÙ ÍÏÖÅÍ ÐÒÅÄÐÏÌÁÇÁÔØ, ÞÔÏ

ÌÀÂÏÅ ËÏÎÅÞÎÏÅ ÞÉÓÌÏ ÎÅÏÂÈÏÄÉÍÙÈ ÎÁÍ ÆÕÎËÃÉÊ × ÜÔÏÍ ÂÁÚÉÓÅ ÅÓÔØ.

óÈÅÍÁ ÓÒÁ×ÎÅÎÉÑ ÞÉÓÅÌ ÂÕÄÅÔ ÒÅËÕÒÓÉ×ÎÏÊ (ÞÔÏÂÙ ÓÒÁ×ÎÉÔØ Ä×Á ÞÉÓÌÁ,

ÍÙ ÏÔÄÅÌØÎÏ ÓÒÁ×ÎÉ×ÁÅÍ ÉÈ ÌÅ×ÙÅ É ÐÒÁ×ÙÅ ÐÏÌÏ×ÉÎÙ, Á ÚÁÔÅÍ ÏÂßÅÄÉÎÑ-

ÅÍ ÒÅÚÕÌØÔÁÔÙ). ðÒÉ ÜÔÏÍ, ËÁË ÞÁÓÔÏ ÂÙ×ÁÅÔ, ÎÁÄÏ ÕÓÉÌÉÔØ ÕÔ×ÅÒÖÄÅÎÉÅ,

ÞÔÏÂÙ ÉÎÄÕËÃÉÑ ÐÒÏÛÌÁ. á ÉÍÅÎÎÏ, ÍÙ ÂÕÄÅÍ ÓÔÒÏÉÔØ ÓÈÅÍÕ Ó 2n ×ÈÏÄÁÍÉ

, . . . , x

, y

, . . . , y

É Ä×ÕÍÑ ×ÙÈÏÄÁÍÉ, ËÏÔÏÒÁÑ ÕËÁÚÙ×ÁÅÔ, ËÁËÏÊ ÉÚ ÔÒ¾È

ÓÌÕÞÁÅ× x < y, x = y ÉÌÉ x > y ÉÍÅÅÔ ÍÅÓÔÏ. (úÄÅÓØ x, y ¡ ÞÉÓÌÁ, ÚÁÐÉ-

ÓÙ×ÁÅÍÏÅ × Ä×ÏÉÞÎÏÊ ÓÉÓÔÅÍÅ ËÁË x

. . . x

É y

, . . . , y

.) ä×Á ×ÙÈÏÄÎÙÈ ÂÉÔÁ

ËÏÄÉÒÕÀÔ ÞÅÔÙÒÅ ×ÏÚÍÏÖÎÏÓÔÉ, Á ÎÕÖÎÏ ÔÏÌØËÏ ÔÒÉ, ÔÁË ÞÔÏ ÅÓÔØ ÎÅËÏÔÏ-

ÒÙÊ ÚÁÐÁÓ. äÌÑ ÏÐÒÅÄÅÌ¾ÎÎÏÓÔÉ ÍÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÐÅÒ×ÙÊ ×ÙÈÏÄÎÏÊ ÂÉÔ

ÉÓÔÉÎÅÎ, ÅÓÌÉ ÞÉÓÌÁ ÒÁ×ÎÙ, Á ×ÔÏÒÏÊ ¡ ÅÓÌÉ x < y. ôÏÇÄÁ ×ÏÚÍÏÖÎÙ ÔÒÉ

×ÁÒÉÁÎÔÁ ÓÉÇÎÁÌÏ× ÎÁ ×ÙÈÏÄÅ: 10 (ÒÁ×ÅÎÓÔ×Ï), 01 (ÐÒÉ x < y) É 00 (ÐÒÉ x >

> y).

ïÂßÑÓÎÉÍ ÔÅÐÅÒØ, ËÁË ÓÏÂÒÁÔØ, ÓËÁÖÅÍ, ÓÈÅÍÕ ÓÒÁ×ÎÅÎÉÑ Ä×ÕÈ 16-ÒÁÚÒÑÄ-

ÎÙÈ ÞÉÓÅÌ. óÏÂÅÒ¾Í ÏÔÄÅÌØÎÏ ÓÈÅÍÕ ÓÒÁ×ÎÅÎÉÑ ÓÔÁÒÛÉÈ 8 ÒÁÚÒÑÄÏ× É ÍÌÁÄ-

ÛÉÈ 8 ÒÁÚÒÑÄÏ×. ëÁÖÄÁÑ ÉÚ ÎÉÈ ÄÁÓÔ ÏÔ×ÅÔ × ÆÏÒÍÅ Ä×ÕÈ ÂÉÔÏ×. ôÅÐÅÒØ

ÉÚ ÜÔÉÈ ÞÅÔÙÒ¾È ÂÉÔÏ× ÎÁÄÏ ÓÏÂÒÁÔØ Ä×Á. (åÓÌÉ × ÓÔÁÒÛÉÈ ÒÁÚÒÑÄÁÈ ÎÅ-

ÒÁ×ÅÎÓÔ×Ï, ÔÏ ÏÎÏ ÏÐÒÅÄÅÌÑÅÔ ÒÅÚÕÌØÔÁÔ ÓÒÁ×ÎÅÎÉÑ; ÅÓÌÉ ÓÔÁÒÛÉÅ ÒÁÚÒÑÄÙ

ÒÁ×ÎÙ, ÔÏ ÒÅÚÕÌØÔÁÔ ÓÒÁ×ÎÅÎÉÑ ÏÐÒÅÄÅÌÑÅÔÓÑ ÍÌÁÄÛÉÍÉ ÒÁÚÒÑÄÁÍÉ.) îÁ-

ÐÉÓÁÎÎÁÑ × ÓËÏÂËÁÈ ÆÒÁÚÁ ÏÐÒÅÄÅÌÑÅÔ ÂÕÌÅ×Õ ÆÕÎËÃÉÀ Ó ÞÅÔÙÒØÍÑ ÂÉÔÁÍÉ

ÎÁ ×ÈÏÄÅ É Ä×ÕÍÑ ÂÉÔÁÍÉ ÎÁ ×ÙÈÏÄÅ, É ÍÏÖÅÔ ÂÙÔØ ÒÅÁÌÉÚÏ×ÁÎÁ ÎÅËÏÔÏÒÏÊ

ÓÈÅÍÏÊ ÆÉËÓÉÒÏ×ÁÎÎÏÇÏ ÒÁÚÍÅÒÁ. ôÁËÉÍ ÏÂÒÁÚÏÍ, ÅÓÌÉ ÞÅÒÅÚ T (n) ÏÂÏÚÎÁ-

ÞÉÔØ ÒÁÚÍÅÒ ÓÈÅÍÙ, ÓÒÁ×ÎÉ×ÁÀÝÅÊ n-ÂÉÔÏ×ÙÅ ÞÉÓÌÁ, ÔÏ ÐÏÌÕÞÁÅÍ ÏÃÅÎËÕ

T (2n) 6 2T (n) + c, ÇÄÅ c ¡ ÎÅËÏÔÏÒÁÑ ËÏÎÓÔÁÎÔÁ, ÚÁ×ÉÓÑÝÁÑ ÏÔ ×ÙÂÏÒÁ ÂÁ-

ÚÉÓÁ. ïÔÓÀÄÁ ÓÌÅÄÕÅÔ, ÞÔÏ T (2

) 6 c

ÐÒÉ ÎÅËÏÔÏÒÏÍ c

. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÄÌÑ

76 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

ÄÏÓÔÁÔÏÞÎÏ ÂÏÌØÛÏÇÏ c

ÍÏÖÎÏ ÄÏËÁÚÁÔØ ÐÏ ÉÎÄÕËÃÉÉ, ÞÔÏ T (2

) 6 c

− c

(ÍÙ ÄÏÌÖÎÙ ÕÓÉÌÉÔØ ÎÅÒÁ×ÅÎÓÔ×Ï, ×ÙÞÔÑ ÉÚ ÐÒÁ×ÏÊ ÞÁÓÔÉ c, ÞÔÏÂÙ ÉÎÄÕË-

ÔÉ×ÎÙÊ ÛÁÇ ÐÒÏÛ¾Ì; ÂÁÚÁ ÉÎÄÕËÃÉÉ ÏÓÔÁÅÔÓÑ ×ÅÒÎÏÊ, ÅÓÌÉ c

ÄÏÓÔÁÔÏÞÎÏ

×ÅÌÉËÏ).

ôÕ ÖÅ ÓÁÍÕÀ ÏÃÅÎËÕ ÍÏÖÎÏ ÏÂßÑÓÎÉÔØ É ÎÁÇÌÑÄÎÏ. îÁÛÁ ÓÈÅÍÁ ÉÍÅÅÔ ×ÉÄ

ÉÅÒÁÒÈÉÞÅÓËÏÇÏ ÄÅÒÅ×Á. îÁ ËÁÖÄÏÍ ÕÒÏ×ÎÅ ÉÚ Ä×ÕÈ Ä×ÕÈÂÉÔÏ×ÙÈ ÓÉÇÎÁÌÏ×

ÐÏÌÕÞÁÅÔÓÑ ÏÄÉÎ. ïÓÔÁ¾ÔÓÑ ×ÓÐÏÍÎÉÔØ, ÞÔÏ × ÐÏÌÎÏÍ Ä×ÏÉÞÎÏÍ ÄÅÒÅ×Å ÞÉÓÌÏ

×ÎÕÔÒÅÎÎÉÈ ×ÅÒÛÉÎ (ËÏÔÏÒÏÅ ÏÐÒÅÄÅÌÑÅÔ ÒÁÚÍÅÒ ÓÈÅÍÙ) ÎÁ ÅÄÉÎÉÃÕ ÍÅÎØÛÅ

ÞÉÓÌÁ ÌÉÓÔØÅ×. (÷ ÔÕÒÎÉÒÅ ÐÏ ÏÌÉÍÐÉÊÓËÏÊ ÓÉÓÔÅÍÅ ÞÉÓÌÏ ÉÇÒ ÎÁ ÅÄÉÎÉÃÕ

ÍÅÎØÛÅ ÞÉÓÌÁ ËÏÍÁÎÄ, ÔÁË ËÁË ÐÏÓÌÅ ËÁÖÄÏÊ ÉÇÒÙ ÏÄÎÁ ËÏÍÁÎÄÁ ×ÙÂÙ×ÁÅÔ.)

÷ÓÅ ×ÎÕÔÒÅÎÎÉÅ ×ÅÒÛÉÎÙ É ×ÓÅ ÌÉÓÔØÑ (ÇÄÅ ÓÒÁ×ÎÉ×ÁÀÔÓÑ Ä×Á ÂÉÔÁ) ÐÒÅÄ-

ÓÔÁ×ÌÑÀÔ ÓÏÂÏÊ ÓÈÅÍÙ ÏÇÒÁÎÉÞÅÎÎÏÇÏ ÒÁÚÍÅÒÁ, ÏÔËÕÄÁ É ×ÙÔÅËÁÅÔ ÏÃÅÎËÁ

T (2

) 6 c

ïÓÔÁÌÏÓØ ÌÉÛØ ÓËÁÚÁÔØ, ÞÔÏ ÄÅÌÁÔØ, ÅÓÌÉ ÒÁÚÍÅÒ ÞÉÓÅÌ (ËÏÔÏÒÙÊ ÍÙ ÏÂÏ-

ÚÎÁÞÁÌÉ ÞÅÒÅÚ n) ÎÅ ÅÓÔØ ÔÏÞÎÁÑ ÓÔÅÐÅÎØ Ä×ÏÊËÉ. ÷ ÜÔÏÍ ÓÌÕÞÁÅ ÍÏÖÎÏ Õ×Å-

ÌÉÞÉÔØ ÒÁÚÍÅÒ ÄÏ ÂÌÉÖÁÊÛÅÊ Ó×ÅÒÈÕ ÓÔÅÐÅÎÉ Ä×ÏÊËÉ (ÎÅ ÂÏÌÅÅ ÞÅÍ × Ä×Á

ÒÁÚÁ) É ÐÏÄÁÔØ ÎÁ ÓÔÁÒÛÉÅ ÒÁÚÒÑÄÙ ×ÈÏÄÏ× ÎÕÌÉ. ïÂÁ ÄÅÊÓÔ×ÉÑ ÐÒÉ×ÏÄÑÔ Ë

Õ×ÅÌÉÞÅÎÉÀ ÒÁÚÍÅÒÁ ÓÈÅÍÙ ÎÅ ÂÏÌÅÅ ÞÅÍ × ËÏÎÓÔÁÎÔÕ ÒÁÚ.

ðÅÒÅÊÄ¾Í Ë ÓÌÏÖÅÎÉÀ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ. (óÔÒÏÇÏ ÇÏ×ÏÒÑ, ÔÕÔ ×ÏÚ-

ÎÉËÁÅÔ ÎÅ ÂÕÌÅ×Á ÆÕÎËÃÉÑ, Á ÆÕÎËÃÉÑ B

× B

→ B

n+1

, ÎÏ ×ÓÅ ÎÁÛÉ ÏÐÒÅÄÅ-

ÌÅÎÉÑ ÏÞÅ×ÉÄÎÏ ÐÅÒÅÎÏÓÑÔÓÑ ÎÁ ÜÔÏÔ ÓÌÕÞÁÊ.)

ôÅÏÒÅÍÁ 26. óÕÝÅÓÔ×ÕÅÔ ÓÈÅÍÁ ÒÁÚÍÅÒÁ O(n), ÏÓÕÝÅÓÔ×ÌÑÀÝÁÑ ÓÌÏ-

ÖÅÎÉÅ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ.

äÏËÁÚÁÔÅÌØÓÔ×Ï. îÁÐÏÍÎÉÍ ÓÍÙÓÌ ÏÂÏÚÎÁÞÅÎÉÑ O(n): ÎÁÍ ÎÁÄÏ ÐÏÓÔÒÏ-

ÉÔØ ÓÈÅÍÕ ÓÌÏÖÅÎÉÑ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ, ÉÍÅÀÝÕÀ ÒÁÚÍÅÒ ÎÅ ÂÏÌÅÅ cn ÄÌÑ

ÎÅËÏÔÏÒÏÇÏ c É ÄÌÑ ×ÓÅÈ n.

÷ÓÐÏÍÎÉÍ, ËÁË ÓËÌÁÄÙ×ÁÀÔ ÞÉÓÌÁ × ÓÔÏÌÂÉË:

01 1

10 0 1

10 1 1

10 1 00

÷ÅÒÈÎÑÑ ÓÔÒÏËÁ ¡ ÂÉÔÙ ÐÅÒÅÎÏÓÁ, ÎÉÖÎÑÑ ¡ ÒÅÚÕÌØÔÁÔ. úÁÍÅÔÉÍ, ÞÔÏ ËÁ-

ÖÄÙÊ ÉÚ ÂÉÔÏ× ÐÅÒÅÎÏÓÁ ÉÌÉ ÒÅÚÕÌØÔÁÔÁ ÏÐÒÅÄÅÌÑÅÔÓÑ ÔÒÅÍÑ ÄÒÕÇÉÍÉ ÂÉ-

ÔÁÍÉ (ÂÉÔ ÒÅÚÕÌØÔÁÔÁ ÒÁ×ÅÎ ÓÕÍÍÅ Ä×ÕÈ ÂÉÔÏ× ÓÌÁÇÁÅÍÙÈ É ÂÉÔÁ ÐÅÒÅÎÏÓÁ

ÐÏ ÍÏÄÕÌÀ 2, Á ÂÉÔ ÐÅÒÅÎÏÓÁ ÒÁ×ÅÎ 1, ÅÓÌÉ ÈÏÔÑ ÂÙ Ä×Á ÉÚ ÜÔÉÈ ÔÒ¾È ÂÉÔÏ×

ÒÁ×ÎÙ 1). ðÏÜÔÏÍÕ ÍÏÖÎÏ ÓÏÓÔÁ×ÉÔØ ÓÈÅÍÕ, ËÏÔÏÒÁÑ ×ÙÞÉÓÌÑÅÔ ÜÔÉ ÂÉÔÙ

ÓÐÒÁ×Á ÎÁÌÅ×Ï É ÉÍÅÅÔ ÒÁÚÍÅÒ O(n).

§3. óÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ× 77

úÁÍÅÔÉÍ, ÞÔÏ ÔÅÏÒÅÍÕ 25 ÌÅÇËÏ ×Ù×ÅÓÔÉ ÉÚ ÔÅÏÒÅÍÙ 26: ÞÔÏÂÙ ÓÒÁ×ÎÉÔØ

ÞÉÓÌÁ x É y, ÓÌÏÖÉÍ ÞÉÓÌÏ (2

− 1) − x (ÔÏ ÅÓÔØ ÞÉÓÌÏ x, × ËÏÔÏÒÏÍ ×ÓÅ

ÅÄÉÎÉÃÙ ÚÁÍÅÎÅÎÙ ÎÕÌÑÍÉ É ÎÁÏÂÏÒÏÔ) É ÞÉÓÌÏ y. åÓÌÉ × ÓÔÁÒÛÅÍ ÒÁÚÒÑÄÅ

ÐÏÑ×ÉÔÓÑ ÅÄÉÎÉÃÁ, ÔÏ y > x, Á ÅÓÌÉ ÎÅÔ, ÔÏ y 6 x. ïÓÔÁ¾ÔÓÑ ÚÁÍÅÔÉÔØ, ÞÔÏ

É ÓÌÏÖÅÎÉÅ, É ÏÂÒÁÝÅÎÉÅ ÂÉÔÏ× × ÞÉÓÌÅ x ÔÒÅÂÕÀÔ ÓÈÅÍ ÌÉÎÅÊÎÏÇÏ ÒÁÚÍÅ-

ÒÁ. ôÁËÉÍ ÏÂÒÁÚÏÍ, ÓÒÁ×ÎÅÎÉÅ ÞÉÓÅÌ Ó×ÏÄÉÔÓÑ Ë ×ÙÞÉÓÌÅÎÉÀ ÂÉÔÁ ÐÅÒÅÎÏÓÁ.

÷ÅÒÎÏ É ÏÂÒÁÔÎÏÅ: ×ÙÞÉÓÌÅÎÉÅ ÂÉÔÁ ÐÅÒÅÎÏÓÁ Ó×ÏÄÉÔÓÑ Ë ÓÒÁ×ÎÅÎÉÀ Ä×ÕÈ

ÞÉÓÅÌ (ÏÂÒÁÔÉÍ × ÏÄÎÏÍ ÉÚ ÓÌÁÇÁÅÍÙÈ ×ÓÅ ÂÉÔÙ).

ôÅÍ ÎÅ ÍÅÎÅÅ ËÏÎÓÔÒÕËÃÉÑ, ÉÓÐÏÌØÚÏ×ÁÎÎÁÑ ÐÒÉ ÄÏËÁÚÁÔÅÌØÓÔ×Å ÔÅÏÒÅ-

ÍÙ 25, ÉÍÅÅÔ ÎÅËÏÔÏÒÙÅ ÐÒÅÉÍÕÝÅÓÔ×Á. îÁÚÏ×¾Í ÇÌÕÂÉÎÏÊ ÓÈÅÍÙ ÍÁËÓÉ-

ÍÁÌØÎÏÅ ÞÉÓÌÏ ÜÌÅÍÅÎÔÏ× ÎÁ ÐÕÔÉ ÏÔ ×ÈÏÄÁ Ë ×ÙÈÏÄÕ. åÓÌÉ ÐÒÅÄÓÔÁ×ÉÔØ

ÓÅÂÅ, ÞÔÏ ÓÉÇÎÁÌ ÎÁ ×ÙÈÏÄÅ ÜÌÅÍÅÎÔÁ ÐÏÑ×ÌÑÅÔÓÑ ÎÅ ÓÒÁÚÕ ÐÏÓÌÅ ÐÏÄÁÞÉ ÓÉÇ-

ÎÁÌÏ× ÎÁ ×ÈÏÄÙ, Á Ó ÎÅËÏÔÏÒÏÊ ÚÁÄÅÒÖËÏÊ, ÔÏ ÇÌÕÂÉÎÁ ÓÈÅÍÙ ÏÐÒÅÄÅÌÑÅÔ

ÓÕÍÍÁÒÎÕÀ ÚÁÄÅÒÖËÕ. ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÒÅËÕÒÓÉ×ÎÁÑ ÓÈÅÍÁ ÓÒÁ×ÎÅÎÉÑ ÉÍÅ-

ÌÁ ÇÌÕÂÉÎÕ O(log n) (ÞÉÓÌÏ ÕÒÏ×ÎÅÊ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏ ÌÏÇÁÒÉÆÍÕ ÒÁÚÍÅÒÁ

×ÈÏÄÁ), × ÔÏ ×ÒÅÍÑ ËÁË ÐÏÓÔÒÏÅÎÎÁÑ ÔÏÌØËÏ ÞÔÏ ÓÈÅÍÁ ÓÌÏÖÅÎÉÑ ÉÍÅÅÔ ÇÌÕ-

ÂÉÎÕ, ÐÒÏÐÏÒÃÉÏÎÁÌØÎÕÀ n (ÂÉÔÙ ÐÅÒÅÎÏÓÁ ×ÙÞÉÓÌÑÀÔÓÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ,

ÓÐÒÁ×Á ÎÁÌÅ×Ï). îÏ ÍÏÖÎÏ ÓÏÅÄÉÎÉÔØ ÜÔÉ Ä×Á ÒÅÚÕÌØÔÁÔÁ:

ôÅÏÒÅÍÁ 27. óÕÝÅÓÔ×ÕÅÔ ÓÈÅÍÁ ÓÌÏÖÅÎÉÑ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ ÒÁÚ-

ÍÅÒÁ O(n) É ÇÌÕÂÉÎÙ O(log n).

äÏËÁÚÁÔÅÌØÓÔ×Ï. ëÁË ÍÙ ×ÉÄÅÌÉ, ÐÒÏÂÌÅÍÁ × ÔÏÍ, ÞÔÏ ÂÉÔÙ ÐÅÒÅÎÏÓÁ ×Ù-

ÞÉÓÌÑÀÔÓÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ, Á ÎÅ ÐÁÒÁÌÌÅÌØÎÏ. åÓÌÉ ÕÄÁÓÔÓÑ ÉÈ ×ÓÅ ×ÙÞÉ-

ÓÌÉÔØ ÓÈÅÍÏÊ ÒÁÚÍÅÒÁ O(n) É ÇÌÕÂÉÎÙ O(log n), ÔÏ ÄÁÌØÎÅÊÛÅÅ ÏÞÅ×ÉÄÎÏ.

ëÁË ÍÙ ÕÐÏÍÉÎÁÌÉ, ×ÙÞÉÓÌÅÎÉÅ ÂÉÔÏ× ÐÅÒÅÎÏÓÁ ÒÁ×ÎÏÓÉÌØÎÏ ÓÒÁ×ÎÅÎÉÀ,

ÔÁË ÞÔÏ ÄÌÑ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÔÅÏÒÅÍÙ ÄÏÓÔÁÔÏÞÎÏ ÎÁÕÞÉÔØÓÑ ÓÒÁ×ÎÉ×ÁÔØ ÐÁ-

ÒÁÌÌÅÌØÎÏ ×ÓÅ ¥ÓÕÆÆÉËÓÙ¥ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ x

. . . x

É y

. . . y

, Ô. Å.

ÄÌÑ ËÁÖÄÏÇÏ i ÓÒÁ×ÎÉÔØ ÞÉÓÌÁ x

i+1

. . . x

É y

i+1

. . . y

÷ÓÐÏÍÎÉÍ, ÞÔÏ ÍÙ ÄÅÌÁÌÉ ÐÒÉ ÓÒÁ×ÎÅÎÉÉ ÞÉÓÅÌ (ÓËÁÖÅÍ, ÄÌÉÎÙ 8). îÁ

ÎÉÖÎÅÍ ÕÒÏ×ÎÅ ÍÙ ÓÒÁ×ÎÉ×ÁÌÉ ÂÉÔÙ:

îÁ ÓÌÅÄÕÀÝÅÍ ÕÒÏ×ÎÅ ÍÙ ÓÒÁ×ÎÉ×ÁÌÉ Ä×ÕÚÎÁÞÎÙÅ ÞÉÓÌÁ

ÚÁÔÅÍ ÞÅÔÙÒ¾ÈÚÎÁÞÎÙÅ

78 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

É, ÎÁËÏÎÅÃ, ×ÏÓØÍÉÚÎÁÞÎÙÅ:

ôÁËÉÍ ÏÂÒÁÚÏÍ, ÄÌÑ ÓÕÆÆÉËÓÏ× ÄÌÉÎÙ 8, 4, 2 É 1 ÒÅÚÕÌØÔÁÔÙ ÓÒÁ×ÎÅÎÉÑ ÕÖÅ

ÅÓÔØ. äÌÑ ÓÕÆÆÉËÓÁ ÄÌÉÎÙ 6 ÒÅÚÕÌØÔÁÔ ÍÏÖÎÏ ÐÏÌÕÞÉÔØ, ËÏÍÂÉÎÉÒÕÑ ÒÅ-

ÚÕÌØÔÁÔ ÓÒÁ×ÎÅÎÉÑ x

y

É x

y

. ðÏÓÌÅ ÜÔÏÇÏ Õ ÎÁÓ ÅÓÔØ

ÉÎÆÏÒÍÁÃÉÑ Ï ÓÕÆÆÉËÓÁÈ ×ÓÅÈ Þ¾ÔÎÙÈ ÄÌÉÎ, É ÓÏÅÄÉÎÑÑ Å¾ Ó ÉÎÆÏÒÍÁÃÉ-

ÅÊ Ó ÐÅÒ×ÏÇÏ ÜÔÁÐÁ, ÐÏÌÕÞÁÅÍ Ó×ÅÄÅÎÉÑ ÐÒÏ ×ÓÅ ÓÕÆÆÉËÓÙ. îÁÐÒÉÍÅÒ, ÄÌÑ

ÓÒÁ×ÎÅÎÉÑ ÓÕÆÆÉËÓÏ× ÄÌÉÎÙ 7, ÔÏ ÅÓÔØ x

. . . x

É y

. . . y

, ÍÙ ÓÏÅÄÉÎÑÅÍ ÒÅ-

ÚÕÌØÔÁÔÙ ÓÒÁ×ÎÅÎÉÑ x

É y

Ó ÒÅÚÕÌØÔÁÔÁÍÉ ÓÒÁ×ÎÅÎÉÑ ÓÕÆÆÉËÓÏ× ÄÌÉÎÙ 6,

ÔÏ ÅÓÔØ x

. . . x

É y

. . . y

÷ ÏÂÝÅÍ ÓÌÕÞÁÅ ËÁÒÔÉÎÁ ÔÁËÁÑ: ÐÏÓÌÅ ¥ÓÕÖÁÀÝÅÇÏÓÑ ÄÅÒÅ×Á¥ ÍÙ ÓÔÒÏÉÍ

¥ÒÁÓÛÉÒÑÀÝÅÅÓÑ¥; ÚÁ k ÛÁÇÏ× ÄÏ ËÏÎÃÁ ÍÙ ÚÎÁÅÍ ÒÅÚÕÌØÔÁÔÙ ÓÒÁ×ÎÅÎÉÑ

×ÓÅÈ ÓÕÆÆÉËÓÏ×, ÄÌÉÎÙ ËÏÔÏÒÙÈ ËÒÁÔÎÙ 2

. üÔÏ ÄÅÒÅ×Ï ÉÍÅÅÔ ÒÁÚÍÅÒ O(n)

É ÇÌÕÂÉÎÕ O(log n), ÞÔÏ ÚÁ×ÅÒÛÁÅÔ ÄÏËÁÚÁÔÅÌØÓÔ×Ï.

úÁÄÁÞÁ 115. ðÏËÁÖÉÔÅ, ÞÔÏ ×ÙÞÉÔÁÎÉÅ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ ÐÏ ÍÏ-

ÄÕÌÀ 2

×ÙÐÏÌÎÑÅÔÓÑ ÓÈÅÍÏÊ ÒÁÚÍÅÒÁ O(n) É ÇÌÕÂÉÎÙ O(log n). (õËÁÚÁÎÉÅ:

×ÙÞÉÔÁÎÉÅ ÌÅÇËÏ Ó×ÏÄÉÔÓÑ Ë ÓÌÏÖÅÎÉÀ, ÅÓÌÉ ÚÁÍÅÎÉÔØ ÎÕÌÉ ÎÁ ÅÄÉÎÉÃÙ É

ÎÁÏÂÏÒÏÔ.)

ôÅÐÅÒØ ÚÁÊÍ¾ÍÓÑ ÕÍÎÏÖÅÎÉÅÍ. óÈÅÍÁ ÕÍÎÏÖÅÎÉÑ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ

ÉÍÅÅÔ 2n ×ÈÏÄÏ× (ÐÏ n ÄÌÑ ËÁÖÄÏÇÏ ÍÎÏÖÉÔÅÌÑ) É 2n ×ÙÈÏÄÏ× ÄÌÑ ÐÒÏÉÚ×Å-

ÄÅÎÉÑ.

ðÏÓÍÏÔÒÉÍ, ËÁËÉÅ ÏÃÅÎËÉ ÄÁ¾Ô ÏÂÙÞÎÙÊ ÓÐÏÓÏÂ ÕÍÎÏÖÅÎÉÑ ÞÉÓÅÌ ÓÔÏÌ-

ÂÉËÏÍ. ÷ Î¾Í ÕÍÎÏÖÅÎÉÅ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ Ó×ÏÄÉÔÓÑ Ë ÓÌÏÖÅÎÉÀ n

ËÏÐÉÊ ÐÅÒ×ÏÇÏ ÞÉÓÌÁ (ÞÁÓÔÉÞÎÏ ÚÁÍÅÎ¾ÎÎÙÈ ÎÁ ÎÕÌÉ × ÚÁ×ÉÓÉÍÏÓÔÉ ÏÔ ÃÉÆÒ

×ÔÏÒÏÇÏ ÞÉÓÌÁ) ÓÏ ÓÄ×ÉÇÁÍÉ.

ðÏÌÕÞÅÎÉÅ ÜÔÉÈ ËÏÐÉÊ ÔÒÅÂÕÅÔ ÓÈÅÍÙ ÒÁÚÍÅÒÁ O(n

) (ÏÂÝÅÅ ÞÉÓÌÏ ÃÉÆÒ

× ËÏÐÉÑÈ) É ÇÌÕÂÉÎÙ O(1). óÌÏÖÅÎÉÅ Ä×ÕÈ 2n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ ÍÙ ÍÏÖÅÍ

×ÙÐÏÌÎÉÔØ Ó ÐÏÍÏÝØÀ ÓÈÅÍÙ ÒÁÚÍÅÒÁ O(n) É ÇÌÕÂÉÎÙ O(log n), ÔÁË ÞÔÏ

ÎÅÏÂÈÏÄÉÍÙÅ n−1 ÓÌÏÖÅÎÉÊ ÍÏÖÎÏ ×ÙÐÏÌÎÉÔØ ÓÈÅÍÏÊ ÒÁÚÍÅÒÁ O(n

) É ÇÌÕ-

ÂÉÎÙ O(log

n) (ÅÓÌÉ ÓËÌÁÄÙ×ÁÔØ ÓÎÁÞÁÌÁ ÐÏÐÁÒÎÏ, ÐÏÔÏÍ ÒÅÚÕÌØÔÁÔÙ ÓÎÏ×Á

ÐÏÐÁÒÎÏ É Ô. Ä.). ïËÁÚÙ×ÁÅÔÓÑ, ÜÔÏÔ ÒÅÚÕÌØÔÁÔ ÍÏÖÎÏ ÕÌÕÞÛÉÔØ. îÁÉÂÏÌÅÅ

ÜËÏÎÏÍÎÙÅ ÓÐÏÓÏÂÙ ÏÓÎÏ×ÁÎÙ ÎÁ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÉ æÕÒØÅ . ó ÉÈ ÐÏÍÏÝØÀ,

ÎÁÐÒÉÍÅÒ, ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÓÈÅÍÕ ÕÍÎÏÖÅÎÉÑ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ, ÉÍÅÀÝÕÀ

ÒÁÚÍÅÒ n log

üÔÉ ÍÅÔÏÄÙ ÄÁÌÅËÏ ×ÙÈÏÄÑÔ ÚÁ ÒÁÍËÉ ÎÁÛÅÇÏ ÏÂÓÕÖÄÅÎÉÑ, ÎÏ Ä×Á ÕÌÕÞ-

ÛÅÎÉÑ ÍÙ ÐÒÉ×ÅÄ¾Í.

§3. óÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ× 79

ôÅÏÒÅÍÁ 28. óÕÝÅÓÔ×ÕÅÔ ÓÈÅÍÁ ÕÍÎÏÖÅÎÉÑ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ

ÒÁÚÍÅÒÁ O(n

) É ÇÌÕÂÉÎÙ O(log n).

äÏËÁÚÁÔÅÌØÓÔ×Ï. ëÁË ÍÙ ÕÖÅ ÇÏ×ÏÒÉÌÉ, ÕÍÎÏÖÅÎÉÅ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉ-

ÓÅÌ Ó×ÏÄÉÔÓÑ Ë ÓÌÏÖÅÎÉÀ n ÔÁËÉÈ ÞÉÓÅÌ, É ÏÓÔÁ¾ÔÓÑ ×ÙÐÏÌÎÉÔØ ÔÁËÏÅ ÓÌÏÖÅ-

ÎÉÅ ÓÈÅÍÏÊ ÒÁÚÍÅÒÁ O(n

) É ÇÌÕÂÉÎÙ O(log n). ëÌÀÞÅ×ÙÍ ÍÏÍÅÎÔÏÍ ÚÄÅÓØ

Ñ×ÌÑÅÔÓÑ Ó×ÅÄÅÎÉÅ ÓÌÏÖÅÎÉÑ ÔÒ¾È ÞÉÓÅÌ Ë ÓÌÏÖÅÎÉÀ Ä×ÕÈ Ó ÐÏÍÏÝØÀ ÐÒÏÓÔÏÊ

ÓÈÅÍÙ ÒÁÚÍÅÒÁ O(n) É ÇÌÕÂÉÎÙ O(1). ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÕÓÔØ ÅÓÔØ ÔÒÉ ÞÉÓÌÁ x,

y É z. åÓÌÉ ÍÙ ÂÕÄÅÍ ÓËÌÁÄÙ×ÁÔØ ÏÔÄÅÌØÎÏ × ËÁÖÄÏÍ ÒÁÚÒÑÄÅ, ÔÏ × ÒÁÚÒÑÄÅ

ÍÏÖÅÔ ÎÁËÏÐÉÔØÓÑ ÌÀÂÁÑ ÓÕÍÍÁ ÏÔ 0 ÄÏ 3, ÔÏ ÅÓÔØ × Ä×ÏÉÞÎÏÊ ÚÁÐÉÓÉ ÏÔ 00

ÄÏ 11. óÆÏÒÍÉÒÕÅÍ ÉÚ ÍÌÁÄÛÉÈ ÂÉÔÏ× ÜÔÉÈ Ä×ÕÈÂÉÔÏ×ÙÈ ÓÕÍÍ ÞÉÓÌÏ u, Á ÉÚ

ÓÔÁÒÛÉÈ (ÓÄ×ÉÎÕÔÙÈ ×ÌÅ×Ï) ¡ ÞÉÓÌÏ v. ôÏÇÄÁ, ÏÞÅ×ÉÄÎÏ, x + y + z = u + v.

ðÏÌÕÞÅÎÉÅ ÃÉÆÒ ÞÉÓÌÁ u É v ÐÒÏÉÓÈÏÄÉÔ ÐÁÒÁÌÌÅÌØÎÏ ×Ï ×ÓÅÈ ÒÁÚÒÑÄÁÈ É

ÔÒÅÂÕÅÔ ÒÁÚÍÅÒÁ O(n) É ÇÌÕÂÉÎÙ O(1).

ôÅÐÅÒØ, ÅÓÌÉ ÎÁÄÏ ÓÌÏÖÉÔØ n ÞÉÓÅÌ, ÍÏÖÎÏ ÒÁÚÂÉÔØ ÉÈ ÎÁ ÔÒÏÊËÉ É ÉÚ

ËÁÖÄÙÈ ÔÒ¾È ÞÉÓÅÌ ÐÏÌÕÞÉÔØ ÐÏ Ä×Á. ÷ ÓÌÅÄÕÀÝÉÊ ËÒÕÇ, ÔÁËÉÍ ÏÂÒÁÚÏÍ,

×ÙÊÄÕÔ (2/3)n ÞÉÓÅÌ (ÐÒÉÍÅÒÎÏ ¡ ÇÒÁÎÉÞÎÙÅ ÜÆÆÅËÔÙ ÂÏÌØÛÏÊ ÒÏÌÉ ÎÅ

ÉÇÒÁÀÔ). éÈ ÓÎÏ×Á ÍÏÖÎÏ ÓÇÒÕÐÐÉÒÏ×ÁÔØ ÐÏ ÔÒÏÊËÁÍ É Ô. Ä. ó ËÁÖÄÙÍ ÕÒÏ×-

ÎÅÍ ÞÉÓÌÏ ÓÌÁÇÁÅÍÙÈ ÕÂÙ×ÁÅÔ × ÐÏÌÔÏÒÁ ÒÁÚÁ, ÔÁË ÞÔÏ ÇÌÕÂÉÎÁ ÓÈÅÍÙ ÂÕÄÅÔ

ÌÏÇÁÒÉÆÍÉÞÅÓËÏÊ. ëÁÖÄÏÅ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÅ ÔÒ¾È ÓÌÁÇÁÅÍÙÈ × Ä×Á ÔÒÅÂÕÅÔ

ÓÈÅÍÙ ÒÁÚÍÅÒÁ O(n) É ÕÍÅÎØÛÁÅÔ ÞÉÓÌÏ ÓÌÁÇÁÅÍÙÈ ÎÁ ÅÄÉÎÉÃÕ, ÔÁË ÞÔÏ

ÐÏÔÒÅÂÕÅÔÓÑ n ÔÁËÉÈ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÊ. éÔÁË, ÜÔÁ ËÏÎÓÔÒÕËÃÉÑ ÉÍÅÅÔ ÏÂÝÉÊ

ÒÁÚÍÅÒ O(n

) É ÇÌÕÂÉÎÕ O(log n). îÁÄÏ ÔÏÌØËÏ ÏÔÍÅÔÉÔØ, ÞÔÏ × ËÏÎÃÅ Õ ÎÁÓ

ÐÏÌÕÞÁÅÔÓÑ ÎÅ ÏÄÎÏ ÞÉÓÌÏ, Á Ä×Á, É ÉÈ ÎÁÐÏÓÌÅÄÏË ÎÁÄÏ ÓÌÏÖÉÔØ ¡ ÞÔÏ ÍÙ

ÕÍÅÅÍ ÄÅÌÁÔØ Ó ÇÌÕÂÉÎÏÊ O(log n) É ÒÁÚÍÅÒÏÍ O(n).

úÁÄÁÞÁ 116. äÏËÁÖÉÔÅ, ÞÔÏ ÓÈÅÍÁ, ×ÙÞÉÓÌÑÀÝÁÑ ÂÕÌÅ×Õ ÆÕÎËÃÉÀ f

ÏÔ n ÁÒÇÕÍÅÎÔÏ×, Õ ËÏÔÏÒÏÊ ÎÉ ÏÄÉÎ ÁÒÇÕÍÅÎÔ ÎÅ Ñ×ÌÑÅÔÓÑ ÆÉËÔÉ×ÎÙÍ,

ÉÍÅÅÔ ÒÁÚÍÅÒ ÎÅ ÍÅÎÅÅ cn É ÇÌÕÂÉÎÕ ÎÅ ÍÅÎÅÅ c log n, ÇÄÅ c > 0 ¡ ÎÅËÏÔÏ-

ÒÁÑ ËÏÎÓÔÁÎÔÁ, ÚÁ×ÉÓÑÝÁÑ ÏÔ ×ÙÂÒÁÎÎÏÇÏ ÎÁÂÏÒÁ ÜÌÅÍÅÎÔÏ×. (áÒÇÕÍÅÎÔ

ÆÕÎËÃÉÉ ÎÁÚÙ×ÁÀÔ ÆÉËÔÉ×ÎÙÍ, ÅÓÌÉ ÏÔ ÎÅÇÏ ÚÎÁÞÅÎÉÅ ÆÕÎËÃÉÉ ÎÅ ÚÁ×É-

ÓÉÔ.)

üÔÁ ÚÁÄÁÞÁ ÐÏËÁÚÙ×ÁÅÔ, ÞÔÏ ÅÓÌÉ × ÐÒÏÃÅÓÓÅ ÕÍÎÏÖÅÎÉÑ Ä×ÕÈ n-ÒÁÚÒÑÄ-

ÎÙÈ ÞÉÓÅÌ ÍÙ ÓÕÍÍÉÒÕÅÍ n ÓÌÁÇÁÅÍÙÈ ÒÁÚÍÅÒÁ n, ÔÏ ÏÃÅÎËÉ O(n

) ÄÌÑ ÒÁÚ-

ÍÅÒÁ É O(log n) ÄÌÑ ÇÌÕÂÉÎÙ, ÐÏÌÕÞÅÎÎÙÅ ÐÒÉ ÄÏËÁÚÁÔÅÌØÓÔ×Å ÔÅÏÒÅÍÙ 28,

ÓÕÝÅÓÔ×ÅÎÎÏ ÕÌÕÞÛÉÔØ ÎÅÌØÚÑ.

ïÄÎÁËÏ ÎÉËÔÏ ÎÅ ÏÂÑÚÙ×ÁÅÔ ÎÁÓ ÓÌÅÄÏ×ÁÔØ ÔÒÁÄÉÃÉÏÎÎÏÍÕ ÓÐÏÓÏÂÕ ÕÍÎÏ-

ÖÅÎÉÑ ÓÔÏÌÂÉËÏÍ ¡ ÏÔËÁÚÁ×ÛÉÓØ ÏÔ ÎÅÇÏ, ÍÙ ÍÏÖÅÍ ÕÍÅÎØÛÉÔØ ÒÁÚÍÅÒ

ÓÈÅÍÙ.

80 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

ôÅÏÒÅÍÁ 29. óÕÝÅÓÔ×ÕÅÔ ÓÈÅÍÁ ÕÍÎÏÖÅÎÉÑ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ

ÒÁÚÍÅÒÁ O(n

log

) É ÇÌÕÂÉÎÙ O(log

n).

äÏËÁÚÁÔÅÌØÓÔ×Ï. îÁÞÎ¾Í Ó ÔÁËÏÇÏ ÚÁÍÅÞÁÎÉÑ. ÷ÙÞÉÓÌÑÑ ÐÒÏÉÚ×ÅÄÅÎÉÅ

Ä×ÕÈ ËÏÍÐÌÅËÓÎÙÈ ÞÉÓÅÌ

(a + bi)(c + di) = (ac − bd) + (ad + bc)i

ÏÂÙÞÎÙÍ ÓÐÏÓÏÂÏÍ, ÍÙ ÄÅÌÁÅÍ ÞÅÔÙÒÅ ÕÍÎÏÖÅÎÉÑ. îÏ ÍÏÖÎÏ ÏÂÏÊÔÉÓØ É

ÔÒÅÍÑ Ó ÐÏÍÏÝØÀ ÔÁËÏÇÏ ÔÒÀËÁ: ×ÙÞÉÓÌÉÔØ ac, bd É (a + b)(c + d), Á ÐÏÔÏÍ

ÎÁÊÔÉ ad + bc ËÁË ÒÁÚÎÏÓÔØ (a + b)(c + d) − ac − bd.

áÎÁÌÏÇÉÞÎÙÊ ÆÏËÕÓ ÍÏÖÎÏ ÐÒÏÄÅÌÁÔØ É ÄÌÑ ÃÅÌÙÈ ÞÉÓÅÌ. òÁÚÏÂØ¾Í

2n-ÂÉÔÏ×ÏÅ ÞÉÓÌÏ ÎÁ Ä×Å n-ÂÉÔÏ×ÙÅ ÞÁÓÔÉ, ÔÏ ÅÓÔØ ÐÒÅÄÓÔÁ×ÉÍ ÅÇÏ × ×É-

ÄÅ a2

+ b. ôÅÐÅÒØ ÚÁÐÉÛÅÍ ÐÒÏÉÚ×ÅÄÅÎÉÅ Ä×ÕÈ ÔÁËÉÈ ÞÉÓÅÌ:

(a2

+ b)(c2

+ d) = ac2

+ (ad + bc)2

+ bd.

ôÅÐÅÒØ ×ÉÄÎÏ, ÞÔÏ ÄÏÓÔÁÔÏÞÎÏ ÎÁÊÔÉ ÔÒÉ ÐÒÏÉÚ×ÅÄÅÎÉÑ ac, bd É (a+b)(c+d),

ÞÔÏÂÙ ÏÐÒÅÄÅÌÉÔØ ×ÓÅ ÔÒÉ ÓÌÁÇÁÅÍÙÈ × ÐÒÁ×ÏÊ ÞÁÓÔÉ ÒÁ×ÅÎÓÔ×Á. ðÏÌÕÞÁÅÔ-

ÓÑ, ÞÔÏ ÕÍÎÏÖÅÎÉÅ Ä×ÕÈ 2n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ Ó×ÏÄÉÔÓÑ Ë ÔÒ¾Í ÕÍÎÏÖÅÎÉÑÍ

n-ÒÁÚÒÑÄÎÙÈ É Ë ÎÅÓËÏÌØËÉÍ ÓÌÏÖÅÎÉÑÍ É ×ÙÞÉÔÁÎÉÑÍ. (îÁ ÓÁÍÏÍ ÄÅÌÅ ÐÒÉ

ÕÍÎÏÖÅÎÉÉ (a+b) ÎÁ (c+d) ÓÏÍÎÏÖÉÔÅÌÉ ÍÏÇÕÔ ÂÙÔØ (n+1)-ÒÁÚÒÑÄÎÙÍÉ, ÎÏ

ÜÔÏ ÎÅ ÓÔÒÁÛÎÏ, ÔÁË ËÁË ÏÂÒÁÂÏÔËÁ ÌÉÛÎÅÇÏ ÒÁÚÒÑÄÁ Ó×ÏÄÉÔÓÑ Ë ÎÅÓËÏÌØËÉÍ

ÓÌÏÖÅÎÉÑÍ.)

äÌÑ ÒÁÚÍÅÒÁ ÓÈÅÍÙ, ÔÁËÉÍ ÏÂÒÁÚÏÍ, ÐÏÌÕÞÁÅÔÓÑ ÒÅËÕÒÓÉ×ÎÁÑ ÏÃÅÎËÁ

S(2n) 6 3S(n) + O(n),

ÉÚ ËÏÔÏÒÏÊ ÓÌÅÄÕÅÔ, ÞÔÏ S(n) = O(n

log

). ÷ ÓÁÍÏÍ ÄÅÌÅ, ÄÌÑ ÕÍÎÏÖÅÎÉÑ

n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ ÔÒÅÂÕÅÔÓÑ ÄÅÒÅ×Ï ÒÅËÕÒÓÉ×ÎÙÈ ×ÙÚÏ×Ï× ÇÌÕÂÉÎÙ log

É ÓÔÅÐÅÎÉ ×ÅÔ×ÌÅÎÉÑ 3. úÁÍÅÔÉÍ, ÞÔÏ ÒÁÚÍÅÒ ÓÈÅÍÙ × ×ÅÒÛÉÎÅ ÐÒÏÐÏÒÃÉÏ-

ÎÁÌÅÎ ÞÉÓÌÕ ÓËÌÁÄÙ×ÁÅÍÙÈ ÂÉÔÏ×. ðÒÉ ÐÅÒÅÈÏÄÅ ÏÔ ÏÄÎÏÇÏ ÕÒÏ×ÎÑ Ë ÓÌÅÄÕ-

ÀÝÅÍÕ (ÂÏÌÅÅ ÂÌÉÚËÏÍÕ Ë ËÏÒÎÀ) ÒÁÚÍÅÒ ÓÌÁÇÁÅÍÙÈ ÒÁÓÔ¾Ô ×Ä×ÏÅ, Á ÞÉÓÌÏ

×ÅÒÛÉÎ ÕÍÅÎØÛÁÅÔÓÑ ×ÔÒÏÅ, ÐÏÜÔÏÍÕ ÏÂÝÅÅ ÞÉÓÌÏ ÜÌÅÍÅÎÔÏ× ÎÁ ÜÔÏÍ ÕÒÏ×-

ÎÅ ÕÍÅÎØÛÁÅÔÓÑ × ÐÏÌÔÏÒÁ ÒÁÚÁ. ôÁËÉÍ ÏÂÒÁÚÏÍ, ÐÒÉ Ä×ÉÖÅÎÉÉ ÐÏ ÕÒÏ×ÎÑÍ

ÏÔ ÌÉÓÔØÅ× Ë ËÏÒÎÀ ÐÏÌÕÞÁÅÔÓÑ ÕÂÙ×ÁÀÝÁÑ ÇÅÏÍÅÔÒÉÞÅÓËÁÑ ÐÒÏÇÒÅÓÓÉÑ ÓÏ

ÚÎÁÍÅÎÁÔÅÌÅÍ 2/3, ÓÕÍÍÁ ËÏÔÏÒÏÊ ×ÓÅÇÏ ÌÉÛØ ×ÔÒÏÅ ÐÒÅ×ÏÓÈÏÄÉÔ Å¾ ÐÅÒ×ÙÊ

ÞÌÅÎ. ïÓÔÁ¾ÔÓÑ ÚÁÍÅÔÉÔØ, ÞÔÏ ÞÉÓÌÏ ÌÉÓÔØÅ× ÒÁ×ÎÏ 3

log

= n

log

ïÃÅÎËÁ ÇÌÕÂÉÎÙ ÔÁËÖÅ ÏÞÅ×ÉÄÎÁ: ÎÁ ËÁÖÄÏÍ ÕÒÏ×ÎÅ ÍÙ ÉÍÅÅÍ ÓÈÅÍÕ

ÓÌÏÖÅÎÉÑ ÇÌÕÂÉÎÙ O(log n), Á ÞÉÓÌÏ ÕÒÏ×ÎÅÊ ÅÓÔØ O(log n).

îÁ ÜÔÏÍ ÍÙ ÚÁ×ÅÒÛÁÅÍ ÚÎÁËÏÍÓÔ×Ï ÓÏ ÓÈÅÍÁÍÉ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅ-

ÍÅÎÔÏ×, ×ÙÐÏÌÎÑÀÝÉÍÉ ÁÒÉÆÍÅÔÉÞÅÓËÉÅ ÏÐÅÒÁÃÉÉ. òÁÓÓÍÏÔÒÉÍ ÔÅÐÅÒØ