АЛГОРИ́ТМА СЛО́ЖНОСТЬ

АЛГОРИ́ТМА СЛО́ЖНОСТЬ, чи­сло­вая харак­те­ри­сти­ка ал­го­рит­ма, из­ме­ряю­щая ли­бо слож­ность его опи­са­ния, ли­бо слож­ность вы­чис­ле­ния с по­мо­щью это­го ал­го­рит­ма. Ни­же рас­смат­ри­ва­ет­ся толь­ко А. с. вы­чис­ле­ния, ко­то­рая ха­рак­те­ри­зу­ет его эф­фек­тив­ность в том или ином смыс­ле. А. с., как пра­ви­ло, яв­ля­ет­ся функ­ци­ей не толь­ко са­мо­го ал­го­рит­ма, но и ис­ход­ных дан­ных (напр., слов). Мно­гие ва­ри­ан­ты А. с. яв­ля­ют­ся мо­но­тон­ны­ми функ­ция­ми на мно­же­ст­ве на­ту­раль­ных чи­сел (длин слов). Са­мым рас­про­стра­нён­ным ва­ри­ан­том А. с. яв­ля­ет­ся А. с. в наи­худ­шем слу­чае, оп­ре­де­ляе­мая как макс. слож­ность ал­го­рит­ма по всем ис­ход­ным дан­ным, дли­на ко­то­рых не пре­вос­хо­дит не­ко­то­ро­го на­ту­раль­но­го чис­ла $n$, рас­смат­ри­вае­мо­го как па­ра­метр. Обыч­но ста­вит­ся во­прос об асим­пто­тич. (при $n\rightarrow \infty$ ) по­ве­де­нии А. с. в наи­худ­шем слу­чае.

Наи­бо­лее важ­ным при­ме­ром А. с. яв­ля­ет­ся вре­мя его ра­бо­ты, из­ме­ряе­мое чис­лом эле­мен­тар­ных ша­гов (опе­ра­ций), со­вер­шае­мых ал­го­рит­мом при пе­ре­хо­де от ис­ход­ных дан­ных к ре­зуль­та­ту ра­бо­ты. Ал­го­рит­мы, вре­мя ра­бо­ты ко­то­рых в наи­худ­шем слу­чае ог­ра­ни­че­но не­ко­торым по­ли­но­мом от дли­ны ис­ход­ных дан­ных, на­зы­ва­ют­ся по­ли­но­ми­аль­ны­ми. Рас­ши­рен­ный те­зис Чёр­ча ут­верж­да­ет, что все ра­зум­ные, в ши­ро­ком ин­туи­тив­ном смыс­ле, уточ­не­ния по­ня­тия ал­го­рит­ма при­во­дят к од­но­му и то­му же клас­су по­ли­но­ми­аль­ных ал­го­рит­мов и что этот класс сов­па­да­ет с клас­сом ал­горит­мов, фак­ти­че­ски реа­ли­зуе­мых на прак­ти­ке. Обе час­ти это­го те­зи­са не яв­ля­ют­ся на­столь­ко бес­спор­ны­ми, как из­на­чаль­ный те­зис Чёр­ча (см. в ст. Ал­го­рит­ми­че­ская про­бле­ма).

Тео­рия А. с. как са­мо­стоя­тель­ная ­науч. дис­ци­п­ли­на на­ча­ла раз­ви­вать­ся в 1960-х гг. од­но­вре­мен­но с раз­ви­ти­ем ком­пь­ю­тер­ных тех­но­ло­гий. В это вре­мя, в ча­ст­но­сти, сфор­ми­ро­ва­лись осн. кон­цеп­ции тео­рии А. с. В нач. 1970-х гг. бы­ла по­строе­на тео­рия пе­ре­бор­ных задач и сфор­му­ли­ро­ва­на цен­траль­ная в этой об­лас­ти про­бле­ма пе­ре­бо­ра (см. Ал­го­рит­мов тео­рия). Бы­ло так­же вве­де­но важ­ней­шее по­ня­тие сво­ди­мо­сти, свя­зан­ное с воз­мож­но­стью из эф­фек­тив­ных ал­го­рит­мов, по­стро­ен­ных для ре­ше­ния од­ной за­да­чи, по­лу­чать эф­фек­тив­ные ал­го­рит­мы для ре­ше­ния др. за­дач.

Совр. тео­рия А. с. име­ет де­ло как с вы­чис­лит. ал­го­рит­ма­ми в пря­мом смыс­ле это­го сло­ва, так и с бо­лее об­щи­ми про­цес­са­ми ал­го­рит­мич. ха­рак­те­ра. По­ми­мо вре­ме­ни ра­бо­ты, час­то изу­ча­ют­ся и др. ви­ды А. с., напр. объ­ём не­об­хо­ди­мой па­мя­ти или ко­ли­че­ст­во пе­ре­дан­ной ин­фор­ма­ции.

Про­бле­ма­ти­ка тео­рии А. с. вклю­ча­ет как по­строе­ние и ана­лиз эф­фек­тив­ных ал­го­рит­мов, так и до­ка­за­тель­ст­во то­го, что в ря­де слу­ча­ев та­кие ал­го­рит­мы не­воз­мож­ны (т. н. про­бле­ма ниж­них оце­нок). В то вре­мя как в пер­вом на­прав­ле­нии дос­тиг­нут су­ще­ст­вен­ный про­гресс, про­бле­ма ниж­них оце­нок ока­за­лась край­не слож­ной.