Спец часть (часть 3) (3 поток) (2015) (by Кибитова) (Ответы на спец часть)

§ .СложностьЗатраты алгоритмаалгоритмакакдляданноговхода,14.  функцияодногоили нескольких числовыхалгебраическаясложностьаргументов.Сложностьв худшем случае. Пусть по входным данным (входу) x алгоритм A вычисляет результат(выход) y. Такое вычисление связано с затратами времени и памяти. Допустим, что достигнуто соглашение о том, как измеряются этизатраты, тогда можно рассмотреть функции затратC AT (x),C AS (x),где верхний индекс T указывает на временные затраты  , S — напространственныезатраты(затратыза§ . Затраты алгоритмадляданного памятивхода и пространственные траты — это синонимы), соответствующие вычислениям, связаннымn(n − 1)(операций обмена↔),x;тобуквыоно колеблетсяот 0 до из английских. ЭтастовприменениемA к входуT и S возникают2словtime —далеевремябудети space— пространство.функций словаможетсортировкаобозначатьсябуквойВидI, отэтиханглийскогобытьоченьнепростым; их трудно исследовать методами математиinsert —вставка.ческого анализа, потому что аргумент x не является, вообще говоря,В этихпримерахуже фактическисказано,что считаетсяразмечисломи непринадлежиткакому-либометрическомупространству.ром входаи затратами.примере . размервхода — характеристикуцелое неотриМожноввестинекоторуюВ неотрицательнуючисловуюn — этопорядокматриц.иВ оцениватьпримере .функцииразмер входа∥цательноеx ∥ возможныхвходовалгоритмазатрат—ссапомовходноечисло(самвход)n.Впримерах.,.количествоисмощью функций, зависящих не от x, а от ∥ x ∥:следуемых операций однозначно определяется по n.

Столь жесткаяГлава . Сложностиалгоритмов какфункции числовых аргументовC ATот(x)размера! ϕ (∥ x ∥),C ASможет(x) ! ψи(∥ неx ∥).иметь места, как(.)зависимость затратвхода  это Избираемуюследует из примера., где размервхода — этодлина nразмероммассива. вхонамивеличину∥·∥принятоназыватьЕслиϕ и ψ не слишком быстро растут при возрастании (числового)В связис этим примером остановимся пока на операциях сравнения.да. В соответствиис n(nнашимразмервходаилидолженхаракаргумента,то эти оценкиобнадеживатьавторапотреби−могут1) замысломКоличествосравнений,требуемоевхудшемслучае,характетеризовать«громоздкость»теляалгоритмаA.2 исходных данных; то, что ∥ x ∥ являетсяризуетрассматриваемыйалгоритмсреди всехсортировкичислом,позволяет говорить о ростеϕ , ψ алгоритмови исследоватьэтот рост.Здесьи далее имеетсяв виду временны́е(связанныес расходованиемвремени),как«имеющийквадратичнуюсложность».ДляприданияэтимсловамВыборразмеравхода — существенныйэтап оцениванияфункцийзааточногоне вре́менные(непостоянные,краткосрочные)затраты.Аналогично—понятиевременна́ясмысладолжнобыть,преждевсего,определеносамотрат; нужна,сложностьи т.

д. во всяком случае, уверенность, что оценки вида (.)сложности.будут нести полезную информацию.  В дальнейшем,предметомбудутне функОпределение..однако,Пусть навозможныхнашеговходах изученияx алгоритмаA опрециизатрат,а некоторыедругиефункцияфункции,которыхвхода).мы скажемделенанеотрицательнаячисловая∥ x ∥о (размерПусть потакжеопределенынеотрицательныефункции C ATобычных(x),слерядапримеров.целочисленныеПредварительноусловимся о некоторыхSC A (x)временных пои пространственныхзатрат алгоритмаA. Тогдавре-a ∈ !,длялитературысложности алгоритмовобозначениях.Пустьменнойпространственнойсложностямифункциит.е. a —ивещественноечисло.Значение ⌊Aa⌋называютсяесть результатокруглечисловогоаргументания a до целого в меньшую сторону: ⌊3,14⌋ = 3, ⌊−3,14⌋ = −4 (этувеличину — целуючастьзаписываюти CкакSTA (n) =max CaAT—(x),S A (n) = max(x)[a]). Соответствен(.)A∥ x ∥=nx ∥=nно, ⌈a⌉ есть результатокругленияa до ∥целогов большую сторону:⌈3,14⌉ = 4, ⌈−3,14⌉ = −3.

Если a — целое, то ⌊a⌋ = ⌈a⌉ = a.(областью изменения n как аргумента функций TA (n) и S A (n) являпростыхпримера.етсяРассмотриммножество тризначенийразмера∥ · ∥). Более полно каждая такаясложностьсложностьюв худшемслучае.Примерименуется.. Исходяиз определенияпроизведенияматриц, мы по  лучаемалгоритмдвухквадратныхматрицпорядкаn, треВместоT (n), S Aумножения(n) мы иногдабудемписать простоT(n),S(n), ес3Aбующийоперацийумножения.Этот алгоритм далее будет обознали ясно, оn какомалгоритмеидет речь.чатьсябуквами MM,от английскихДва примечанияк определению.. слов matrix multiplication — матTричноеумножение.) ЗначениеC A (x) есть в подавляющем большинстве случаев числокаких-то операций, а C AS (x) — число хранимых величин какого-то тиПример .. Один из очевидных алгоритмов распознавания пропа, поэтому предположениео целочисленности значений этих функстоты данного n ∈ "+ , который мы будем называть алгоритмом пробций вполне естественно. Без этого предположения в (.) пришлосьных делений,состоит в выяснении того, имеется ли среди чисел(количества.зависит от размеров ее операндов, это относится и к арифметиче(областьюизмененияn как аргументафункцийTA (n) и S A (n)являОтметимеще, что,говоря,время (например,выполненияоперациискимоперациям,и к вообщеоперациисравнениядлинныечисется множествозначенийразмера ∥это· ∥).

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

простоАналогичнодело есобВместо сложностью;TA (n),S A (n) мыиногдабудемичемписатьT(n),S(n),ственнойздесь,прежденаходитьсложность,надостоитспространственнымизатратамиисоответственноспространли ясно, чтоо какомалгоритмеидет речь.решить,является«единицейхранения»: скажем, при умноженииственнойсложностью;здесь,преждесложность, надопримечанияк определению..чем находитьдвухДваматрицмы можемполучить матрицус элементами, которые заTрешить,чтоявляется«единицейхранения»:скажем,приумножении) ЗначениеC A (x)длинно,есть в подавляющембольшинствеслучаевчислописываютсяболеечемэлементыисходныхматриц.ОднакоSполучить матрицу с элементами, которые задвухматрицмыможемкаких-тоопераций,аC(x)—числохранимыхвеличинкакого-тотиAдовольно частосчитается,что элементырезультат исходныхоперацииматриц.всегда умещаетсяписываютсяболеедлинно,чемОднакопа, поэтому предположение о целочисленности значений этих функводной ячейке..Сложностиалгоритмовкак функциичисловыхдовольночастосчитается,чтоэтогорезультатоперациивсегдаумещаетсяцийГлававполнеестественно.Безпредположенияв (.) аргументовпришлось  Иногдаприходитсяотвлекатьсяоттого,чтодесятичнаяили двоичв одной ячейке.наязаписьиррациональногочисламожетбытьразмещенавтоячейбыиспользоватьsup вместоmax,чтосделаломногиерассуждениятируемыхмассивовсчитаютсяпопарноразличными.Еслинеоговоренопротивное,Иногдаприходитсяотвлекатьсяот нетого,что быдесятичнаяили двоичвсегда идето сортировкепо возрастанию.входакаждойалгебраическойиз сортировоккекакого-либоустройства.Болеетого, вбытьтеорииоречьсложностиболеетяжеловесными.наязаписьиррациональногочислане Размеромможетразмещенав ячеймы без специального упоминания считаем число n элементов массива.сложностикакразделеалгебрырассматривают,например,алгорит)Видимо,вместо«сложностьвхудшемслучае»правильнеебыке какого-либо устройства.

Более того, в теории алгебраическоймы,применимыек элементампроизвольногоабстрактногокольцало бысказать«сложностькак затратыв худшемнапример,случае», нотаковасложностикак разделеалгебрырассматривают,алгоритпринятаятерминология.Мы пока§ абстрактного) не рассматриваемилиполя, здесьи вопроспредставленииэтих(доэлементовв реальномкоммы,применимыек оэлементампроизвольногокольцасложностьсреднем,и поэтому,не этихопасаясьпутаницы,будем назыпьютерев абстрактноймашинене элементовобсуждаетсявообще.илиполя, илии ввопросо представлениив реальномкомватьсложностьвхудшемслучаепростосложностью.пьютере или в абстрактной машине не обсуждаетсявообще.  Определение.. ПустьMM,функцияC AT (x)в определении. РасотраВернемся к алгоритмамTD, I Tизпримеров., ., ..ОпределениеПусть функцияC A (x)определении.операцийотражаетзатратына ..выполнениелишь какого-тоодногосмотримвначалевременныесложностиTMMв(n),TTD (n), TтипаI (n).

Получажаетзатраты 3на выполнениекакого-тоодноготипа операцийn(nэти−лишь1)операциив предположении,что всетребуютодинаковоговремеемT(n)=nиT(n)=.ДляT(n)унаснетстольпростойMMITDвнипредположении,чтозависящеговсе этитребуютодинаковоговреме2 операциивыполнения, неот видаи размераоперандов,и этоформулы.Заметим,например,чтодлязначенийnотдомынивыполнения,зависящегоот вида и размераи этовремяравно 1. неТогдасоответствующаяфункцияоперандов,TA (n) — этосложимеем равно 1. Тогда соответствующая функция TA (n) — это сложвремяность почислу операций рассматриваемого типа.

Привлечение в каSчислуностьпооперацийрассматриваемогов ка- доn: отражающей  только типа. Привлечение честве CSA (x) функции,количествохранимыхчестведоTTDC(n):величин отражающей иноготолько количество хранимых типа, привоA (x) функции,полнительныхтогоилификсированногополнительных величин того или иного фиксированного типа, приводитк пространственнойчислу величин рассматИзменениеэтой функциисложностипри n → ∞S можнотак:A (n) по охарактеризовать$диткпространственнойсложностиS(n)почислувеличинрассматAГлава.Сложностиалгоритмовкакфункциичисловыхаргументовриваемоготипа.для любых n значение этой функции не превосходит ⌊ n⌋ − 1, и найриваемого типа.дутся сколь угодно большие n, для которых ее значение равно  ваяэтим предположениео равнозатратностивсех рассматриваемых$ Такуюсложность называюталгебраическойсложностью по чис⌊операцийn⌋ − 1.

исложностьТакуюназываюталгебраическойсложностьюпо чисравнообъемностивсехучитываемыхвеличин.Алгебраилу Главаоперацийиличислувеличинрассматриваемоготипа,подчерки. СложностиалгоритмовкакфункциичисловыхаргументовВпримерах.и.невозникаетнеобходимостивхранениилуоперацийиличислувеличинрассматриваемоготипа,подчерки  ческую сложность арифметических алгоритмов по числу умноженийбольшихобъемоввеличинсверхобъемавхода(сортировкапростыи деленийназываютсложностью.Из основныхваяэтимпредположениео равнозатратностивсех рассматриваемыхнапример,[].мультипликативной См.,См.,например,[].мивставкаминетребуетдополнительногомассива).Дополнительнаяарифметическихоперацийумножениеиделениеявляютсянаиболееопераций и равнообъемности всех учитываемых величин.Алгебраидорогими,и прирассмотренииарифметическихалгоритмов переменныхчастопамять,еслии нужна,— это несколькодополнительныхческуюсложностьарифметическихалгоритмовпочислу умноженийинтересуютсяименно (алгебраической)сложноалгоритмом. мультипликативнойи(ячеек),деленийиспользуемыхназывают мультипликативнойсложностью.