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

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

Текст из файла

§ .СложностьЗатраты алгоритмаалгоритмакакдляданноговхода,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.

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

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)