[Dangdang.com Подлинная книга](Легко изучить номер
Вес товара: ~0.7 кг. Указан усредненный вес, который может отличаться от фактического. Не включен в цену, оплачивается при получении.
Описание товара
 | |||
 |  |  |  |
 |  |  |  |
 |  |  |  |
| |||
| | | |
| | | |
| | | |
Новая работа от автора супербестселлера «Шаблоны дизайна Dahua»!База пользователей шире, стиль письма остается прежним, а технические накопления глубже.Это обязательно вызовет повальное увлечение национальными структурами данных!
граница
Глава 1  Структура данных неполноризм
1.1 вступительное слово
1.2  как вы изучаете структуру данных?
1.3  Происхождение структуры данных
1.4  Основные понятия и термины
1.4.1  Данные
1.4.2  элемент данных
1.4.3 элемент данных
1.4.4  объект данных
1.4.5  Структура данных
1.5  логическая структура и физическая структура
1.5.1  логическая структура
1.5.2  физическая структура
1.6  Абстрактный тип данных
1.6.1  Тип данных
1.6.2  Абстрактный тип данных
1.7  Сводка обзора
1.8 заключительное предложение
Глава 2   алгоритм
2.1 вступительное слово
2.2  Структура данных и отношения алгоритма
2.3  сравнение двух алгоритмов
2.4  определение алгоритма
2,5  характеристики алгоритма
2.5.1  входной вывод
2.5.2 Конечность
2.5.3  Определение
2.5.4  осуществимость
2.6  требования к проектированию алгоритма
2.6.1  Правильность
2.6.2  читаемость
2.6.3  надежность
2.6.4 Высокая эффективность использования времени и малая емкость хранилища
2.7  метод измерения эффективности алгоритма
2.7.1&Метод статистики NBSP;
2.7.2  оцененные методы оценки
2.8  постепенный рост функции
2.9 сложности времени алгоритма
2.9.1  определение сложности алгоритма времени
2.9.2  управляйте методом оценки O -Order
2.9.3 постоянный шаг
2.9.4 линейные шаги
2.9.5  сочетание
2.9.6 квадратный шаг
2.10  общая сложность времени
2.11 *плохая ситуация и средняя ситуация
2.12  Сложность пространства алгоритма
2.13  Сводка обзора
2.14 заключительное предложение
Глава 3  линейная таблица
3.1 вступительное слово
3.2  Определение линейных таблиц
3.3  Абстрактная линейная таблица типа данных
3.4  Структура хранения заказов линейных таблиц
3.4.1  Последовательное определение хранения
3.4.2  метод последовательного хранения
3.4.3  Длина данных и разница в длине линейной таблицы
3.4.4  метод расчета адреса
3,5  вставьте и удалите последовательную структуру хранения
3.5.1  Получить работу элемента
3.5.2  операция вставки
3.5.3  Удалить операцию
3.5.4  преимущества и недостатки линейной структуры хранения заказа поверхности
3.6  цепная структура хранения линейных таблиц
3.6.1  решение недостаточной структуры хранения в порядке
3.6.2  определение структуры хранения линейного браслета
3.6.3 Сходства и различия между указателем головы и узлом головы
3.6.4 Описание кода структуры хранения цепочки линейных списков
3.7 Чтение из односвязного списка
3.8 Вставка и удаление односвязного списка
3.8.1 Вставка в односвязный список
3.8.2 Удаление односвязного списка
3.9 Создание всего односвязного списка
3.10 Удалить весь односвязный список
3.11 Преимущества и недостатки структуры односвязного списка и последовательной структуры хранения.
3.12  Статический связанный список
3.12.1  вставьте работу статического связанного списка
3.12.2  операция удаления статического связанного списка
3.12.3  Статические преимущества и недостатки связанных списков
3.13  Круглый связанный список
3.14 два -связанный список
3.15  Сводка обзора
3.16 заключительное предложение
Глава 4 стек и очередь
4.1 вступительное слово
4.2  определение
4.2.1  определение
4.2.2  форма изменений в стеке стека
4.3  стек абстрактный тип данных
4.4  Структура хранения последовательностей NBSP;
4.4.1  Структура хранения последовательностей стека
4.4.2   Структура хранения последовательностей стека в операции стека
4.4.3  Структура хранения последовательностей стека из операции стека
4,5  Два места обмена стеком
4.6  Структура хранения цепи и реализация стека
4.6.1 цепная структура хранения стека
4.6.2  Структура хранения цепи стека в операции стека
4.6.3  Структура хранения цепи стека из работы стека
4.7&Функция стека NBSP;
4,8&Приложение стека NBSP;—— рекурсивный
4.8.1  Фибонарическое число
4.8.2  рекурсивное определение
4.9&Приложение стека NBSP;—— четыре операционных выражения для стоимости
4.9.1 Определение суффиксной (обратной польской) нотации
4.9.2&Nbsp; страдание выражений суффикса
4.9.3  Среднешнее выражение экспрессии Rotemon Expression
4.10  Определение очереди
4.11  Абстрактные типы данных очереди
4.12 очередь циркуляции
4.12.1&Nbsp; недостаточное хранение заказа очереди
4.12.2  Определение очереди циркуляции
4.13  Структура хранения цепи и реализация очередей
4.13.1  операция регистрации цепочки цепочки очередей
4.13.2  Структура хранения цепочки очередей вне работы команды
4.14  Сводка обзора
4.15 заключительное предложение
Глава 5 строка
5.1 Вступительное слово
5.2  определение строки
5.3&Сравнение строк NBSP;
5.4  Строковой абстрактный тип данных
5,5  Структура хранения строк
5.5.1  Структура хранения порядка удара
5.5.2 цепная структура хранения строки
5,6  Алгоритм простого соответствия режима
5,7 Алгоритм соответствия режима NBSP;
5.7.1  принцип алгоритма соответствия режима NBSP;
5.7.2  следующее вывод значения массива
5.7.3  Режим соответствия режима NBSP;
5.7.4  Улучшение алгоритма соответствующего режима KMP
5.7.5&Nbsp; деривация значения массива NextVal
5.8  Сводка обзора
5.9 заключительное предложение
Глава 6 дерево
6.1 вступительное слово
6.2  определение дерева
6.2.1  классификация узлов
6.2.2  отношения между узлами
6.2.3  другие связанные концепции дерева
6.3&Nbsp; абстрактный тип данных дерева
6.4  Структура хранения деревьев
6.4.1  воспитание детей
6.4.2  дети
6.4.3  Детский брат метод
6,5  определение двоичного дерева
6.5.1  Особенности бинарных деревьев
6.5.2  специальное двоичное дерево
6.6  природа бинарного дерева
6.6.1 двоичное дерево природа 1
6.6.2 двоичное дерево природа 2
6.6.3 двоичное дерево природа 3
6.6.4 двоичное дерево природа 4
6.6.5  Двоичное дерево природа 5
6.7  Структура хранения двоичного дерева
6.7.1  структура хранения с гладкой последовательности двоичных деревьев
6.7.2  двоичный связанный список
6.8&Nbsp; пересеченный байер
6.8.1  принцип обхода
6.8.2&Методы метода NBSP;
6.8.3  Алгоритм предварительного заказа
6.8.4  Алгоритм обхода средней последовательности
6.8.5 алгоритм обхода после -
6.8.6 результаты обхода дедусера
6.9  установление бинарного дерева
6.10  КЛЮЧЕВОЕ ДВЕЙНАЯ ДЕРЕВО
6.10.1  КЛЮЧЕЙ
6.10.2  КЛЮЧЕВАЯ ДЕРЕВАНИЯ
6.11  дерево, лесное и бинарное обращение деревьев
6.11.1 дерево превращается в двоичное дерево
6.11.2 Форест превращается в бинарное дерево
6.11.3  двоичное дерево преобразовывается на дерево
6.11.4  двоичное дерево превращается в лес
6.11.5&Nbsp; проход дерева и леса
6.12 hofman tree и его применение
6.12.1 hffman
6.12.2&Nbsp; определение дерева Hefman и принцип
6.12.3  Код Хофман
6.13  Сводка обзора
6.14 заключительное предложение
Глава 7 
7.1 вступительное слово
7.2&Определение NBSP; график
7.2.1  определение различных диаграмм
7.2.2&Nbsp; вершина фигуры и взаимосвязь между границей
7.2.3  Связанный с диаграммой термин
7.2.4  определение и резюме термина
7.3  Абстрактные типы данных
7.4  Структура хранения рисунка
7.4.1 соседняя матрица
7.4.2 соседняя таблица
7.4.3 Перекрестный список
7.4.4  прилегающие несколько таблиц
7.4.5 набор краев
7,5  прохождение
7.5.1 Обход в глубину
7.5.2 приоритет приоритета
7,6 *дерево небольшого поколения
7.6.1 Алгоритм Прима
7.6.2 Алгоритм Краскала
7.7 *короткий путь
7.7.1 Алгоритм Дейкстры
7.7.2 Алгоритм Флойда
7,8  сортировка топологии
7.8.1  топология сортировка введения
7.8.2  алгоритм сортировки топологии
7.9  Ключевой путь
7.9.1  принцип алгоритма ключевого пути
7.9.2  алгоритм ключевого пути
7.10  Сводка обзора
7.11 заключительное предложение
Глава 8 найти
8.1 вступительное слово
8.2 найти введение
8.3  Последовательный поиск таблицы
8.3.1  Алгоритм поиска последовательных таблиц
8.3.2  Последовательная таблица оптимизация поиска
8.4 Поиск по упорядоченному списку
8.4.1 сгибание половины, чтобы найти
8.4.2  поиск интерполяции
8.4.3 fibonacci найти
8,5  Поиск линейного индекса
8.5.1 плотный индекс
8.5.2&Индекс секции NBSP;
8.5.3 инвертированный индекс
8,6  двоичное дерево сортировки
8.6.1  операция поиска бинарной сортировки
8.6.2  операция вставки двоичного дерева сортировки
8.6.3  Дерево бинарного дерева сортировки
8.6.4  Резюме бинарного дерева сортировки
8.7 Сбалансированное двоичное дерево (дерево AVL)
8.7.1  Сбалансированный принцип реализации бинарных деревьев
8.7.2  Алгоритм реализации бинарных деревьев баланса
8.8 Дерево многопутевого поиска (B-дерево)
8.8.1  2-3 дерево
8.8.2  2-3-4 дерево
8.8.3 b дерево
8.8.4 b дерево
8.9 Обзор поиска хеш-таблицы (хеш-таблица)
8.9.1  Sanda List
8.9.2  Список Санды
8.10  построение метода функции задержки
8.10.1  метод прямого сайта
8.10.2 метод цифрового анализа
8.10.3&Nbsp; ложная клыка Франция
8.10.4 
8.10.5 за исключением оставшегося численного метода
8.10.6  метод случайного числа
8.11  метод борьбы с конфликтами распределения
8.11.1  метод открытия настройки
8.11.2&Метод функции nbsp;
8.11.3  метод адреса цепного адреса
8.11.4  метод общественного переполнения
8.12  Список Санды поиск реализации
8.12.1  Список диспастеров найти внедрение алгоритма
8.12.2  Список диспастеров Найти анализ производительности
8.13  Сводка обзора
8.14 заключительное предложение
Глава 9  сортировка
9.1 вступительное слово
9.2  Основные понятия и классификация сортировки
9.2.1  стабильность сортировки
9.2.2  Внутренняя сортировка и внешняя сортировка
9.2.3  структура и функция, используемая для сортировки
9.3  Сортировка пузырьков
9.3.1 *Простая реализация сортировки
9.3.2  алгоритм сортировки пузырьков
9.3.3  Оптимизация сортировки пузырьков
9.3.4  анализ сложности сортировки пузырьков
9.4 Простая сортировка выбора
9.4.1 Простой алгоритм сортировки выбором
9.4.2 Простой анализ сложности сортировки выбора
9.5 вставьте непосредственно в сортировку
9.5.1  подключите алгоритм сортировки напрямую
9.5.2  анализ сложности сортировки в порядке
9.6  Сортировка холма
9.6.1&Принципы сортировки NBSP;
9.6.2 Алгоритм сортировки холма
9.6.3  анализ сложности сортировки Hill
9.7 stocked order
9.7.1 алгоритм заказа по укладке
9.7.2  Анализ сложности сложности пакета
9.8  слияния и сортировка
9.8.1  Алгоритм сортировки слияния
9.8.2  анализ сложности слияний и сортировки
9.8.3  нерекурсивно реализованное слияние и сортировку
9.9 быстрая сортировка
9.9.1  Алгоритм быстрой сортировки
9.9.2  Анализ сложности сортировки сортировки
9.9.3 быстрая оптимизация сортировки
1Оптимизировать выбор
2Оптимизируйте ненужный обмен
3Оптимизировать схему сортировки, когда десятичная группа
4Оптимизированная рекурсивная операция
9.10  Сводка обзора
9.11 заключительное предложение
Приложение  ссылка
Глава 2   алгоритм
начинать
Показать алгоритм:
Алгоритм — это описание шагов по решению конкретной проблемы, представленное в компьютере в виде конечной последовательности инструкций, причем каждая инструкция представляет собой одну или несколько операций.
2.1 вступительное слово
Всем привет.
После последнего урока одноклассник сказал мне: «Учитель, после прослушивания вашего урока я чувствую, что структура данных — это ничто, и вы преувеличили ее сложность.
Да, я вроде бы подчеркнул, что структуры данных более умственные, но на последнем занятии я особо сложных вещей не придумал.Дело не в том, что я не хочу, а в том, что это не нужно. Я обману тебя на первом занятии. Тогда что ты собираешься делать в будущем?Не станет ли больше людей, прогуливающих занятия?Видите ли, количество людей, пришедших сегодня, почти такое же, как и в первый раз, и никто еще не спал.
Контент, который мы представляем сегодня, стал сложнее.Вы готовы?
2.2  Структура данных и отношения алгоритма
Наш курс называется «Структура данных», но мы много раз будем говорить об алгоритмах и взаимосвязях между ними.На рынке также есть много книг под названием“ Структура данных и анализ алгоритма”Такое имя.
Кто-то может спросить, вы говорите только о структуре данных или вы говорите о ней вместе с алгоритмами?Какова связь между ними?Зачем объединять их?
Как ответить на этот вопрос.Например, сегодня день рождения вашей девушки. Вы планируете пригласить ее на романтический мюзикл. Когда вы приходите в театр, вы смотрите вверх.—&- Начало «Лян Шаньбо» в 18:00.Ну как такое могло быть?Спросив, я узнал, что актер, сыгравший Чжу Интая, сегодня заболел, поэтому Лян Шаньбо выступил с моноспектаклем.Очень смешно, что еще посмотреть?Итак, вы планируете посмотреть фильм о любви.Когда я пришел в кинотеатр, я увидел афишу—&- «Ромео», если название было написано неправильно, я спросил и узнал, что актер, игравший Джульетту, ушел из спектакля на полпути, потому что ему не понравился низкий гонорар за исполнение.Учитывая, что съемки уже начались, продюсер решил назвать фильм «Ромео», в котором преимущественно рассказывается история путешествия героя.Эй, как мне посмотреть этот фильм?
Фактически, структуры данных и алгоритмы имеют схожие отношения.Конечно, можно говорить только о структурах данных. Мы можем представить несколько важных структур данных за короткое время.Прослушав его, вы, вероятно, понятия не имеете, в чем заключается польза этих структур данных.Но если мы поговорим о соответствующих алгоритмах, то вы обнаружите, что даже начнете вздыхать: о, предшественники в компьютерной индустрии действительно были очень потрясающими людьми. Они сделали многие, казалось бы, трудные или неразрешимые проблемы такими чудесными и волшебными.
Может быть, от этого, медленно часть вас начнет забрать ваш объект поклонения от красивого парня*, что“ брат&Rdquo&Ldquo; сестра”Если мы передадим это этим бородатым или лысым старикам, то я был бы очень рад.Более того, это, очевидно, признак зрелости. Я надеюсь, что таких людей будет больше, чтобы спасти индустрию программного обеспечения нашей страны.
Но опять же, теперь многие университеты, обычно это обычно&Ldquo; алгоритм”Он разделен на отдельный курс, то есть в курсе «Структура данных», даже если алгоритмы обсуждаются, это помогает понять структуру данных, и не все аспекты алгоритмов будут обсуждаться подробно.Наши курсы также построены по этому принципу.
2.3  сравнение двух алгоритмов
Каждый изучил компьютерный язык. Независимо от того, какой из них вы выучите, хорошо вы его усвоили или нет, вы можете написать несколько небольших программ.Теперь прошу вас написать запрос 1 2 3…&Как написать процедуру Hellop; 100 результатов?
Большинство людей сразу напишут следующий код на C (или код на других языках):
int i, sum = 0, n = 100;
для (i = 1; я<= n; i)
{{
Sum = sum i;
}
Printf (printf" %d", Сумма);
Это одна из самых простых компьютерных программ. Это алгоритм. Я не буду объяснять смысл этого кода.Проблема в том, что ваша интуиция подсказывает это, но действительно ли это хорошо?Это *эффективно?
На этот раз мне предстоит рассказать историю детства великого математика Гаусса. Может быть, вы уже слышали это раньше, но с таким же успехом можете еще раз почувствовать, как гений проявил свой талант и талант.
Говорят, что Гаусс родился в маленькой деревне в Германии в 18 веке. Однажды, когда он учился в начальной школе, класс был очень хаотичным. Как и одноклассники внизу, которые шепчутся или играют со своими мобильными телефонами, учитель был очень зол, и последствия, естественно, были серьезными.Поэтому учитель попросил каждого ученика после школы посчитать 1 2.&Результат Hellip; 100, который может рассчитать, кто первым идет домой.
Конечно, гениев такой вопрос не поставит в тупик.Гаусс быстро нашел ответ: 5050. Учитель был очень удивлен, потому что он, должно быть, сдал 1 2=3, 3 3=6, 6 4=10,…&Привет; 4950 100 = 5050 рассчитывается в течение длительного времени.Может быть, это было два или три раза из -за страха ошибок.Но почему этот подросток может получить результат так быстро?
Гаусс объяснил:
Программа реализуется следующим образом:
int i, sum = 0, n = 100;
сумма = (1 n) * n/2;
Printf (printf"%d", Сумма);
Чудо есть чудо. Используемый им метод эквивалентен другому алгоритму поиска арифметической последовательности. Его можно использовать не только для прибавления 1 к 100, но и для прибавления к одной тысяче, десяти тысячам или ста миллионам (тип целочисленной переменной необходимо изменить на long, иначе произойдет переполнение), что происходит мгновенно.Но если вы сейчас воспользуетесь программой, то станет очевидно, что компьютеру придется выполнить тысячу, десять тысяч или сто миллионов операций сложения.Кажется реальностью то, что человеческий мозг может считать быстрее, чем компьютер.
2.4&NBSP; определение алгоритма
Что такое алгоритм?Алгоритм описывает метод решения проблемы.Слово «алгоритм» впервые появилось в «Индийской числовой арифметике», написанной персидским математиком Аль-Хорезми в 825 году нашей эры (что соответствует эпохе династии Тан в Китае).Общепринятое определение алгоритма сегодня следующее:
Алгоритм — это описание шагов по решению конкретной проблемы, представленное в компьютере в виде конечной последовательности инструкций, причем каждая инструкция представляет собой одну или несколько операций.
В только что приведенном примере мы также увидели, что для данной проблемы может существовать несколько алгоритмов ее решения.
Тогда я должен вас спросить, существует ли универсальный алгоритм?Этот вопрос на самом деле очень дебильный, как и вопрос, существует ли лекарство, способное вылечить все болезни!
Проблемы в реальном мире очень странные, и, конечно, алгоритмы постоянно меняются. Не существует универсального алгоритма, способного решить все проблемы.Даже для решения небольшой задачи очень хороший алгоритм может не подойти.
В определении алгоритма упоминаются инструкции, которые могут выполняться вычислительными устройствами, такими как люди или машины.Это может быть компьютерная инструкция или наш повседневный язык.
Чтобы решить определенную проблему или определенный тип задач, инструкции должны быть выражены в виде определенной последовательности операций. Последовательность операций включает в себя набор операций, и каждая операция выполняет определенную функцию.Это алгоритм.
2,5&NBSP; характеристики алгоритма
Алгоритмы имеют пять основных характеристик: вход, выход, конечность, достоверность и осуществимость.
2.5.1&NBSP; входной вывод
Входные и выходные характеристики относительно легко понять, алгоритмы имеют ноль или более входных данных.Хотя входные параметры необходимы для большинства алгоритмов, в отдельных случаях, например, при печати&Ldquo; Helloworld!”Такой код не требует никаких входных параметров, поэтому входные данные алгоритма могут быть нулевыми.Алгоритм имеет по крайней мере один или несколько выходов. Алгоритм должен выводить результат. Если нет необходимости в выводе, почему вы используете этот алгоритм?Выходные данные могут быть в форме распечатки или возврата одного или нескольких значений.
2.5.2 Конечность
Конечность: означает, что алгоритм завершается автоматически после выполнения ограниченного числа шагов без бесконечных циклов, и каждый шаг завершается в течение приемлемого времени.В действительности часто пишут код бесконечного цикла, а значит, он не удовлетворяет конечности.Конечно, понятие конечности здесь не чисто математическое, а разумное и приемлемое в практических приложениях.“Есть границы”.
2.5.3&NBSP; Определение
Детерминированный: каждый шаг алгоритма имеет определенное значение, и не будет никакой двусмысленности.При определенных условиях алгоритм имеет только один путь выполнения, и одни и те же входные данные могут иметь только лучший выходной результат.Каждый шаг алгоритма определен точно и без двусмысленности.
2.5.4&NBSP; осуществимость
Реализуемость: каждый шаг алгоритма должен быть выполнимым, то есть каждый шаг может быть выполнен путем выполнения ограниченного количества раз.Реализуемость означает, что алгоритм можно преобразовать в программу, запустить на компьютере и получить правильные результаты.Хотя существуют чрезвычайно сложные алгоритмы, которые не реализованы в современном компьютерном мире, это не означает, что их невозможно реализовать теоретически, а потому, что они слишком сложны. Наши нынешние методы программирования, инструменты и мозги ограничивают эту работу. Однако все это проблемы из области теоретических исследований и не входят в рамки того, что нам необходимо сейчас рассматривать.
2.6&NBSP; требования к проектированию алгоритма
Как мы только что говорили, алгоритм не идеален.Другими словами, для решения одной и той же задачи может существовать несколько алгоритмов.Это может разочаровать тех студентов, которые круглый год принимают только вопросы со стандартными ответами. Они очень надеются, что есть стандартный ответ, правильный только один, его просто запомните и применяйте при необходимости.Но, несмотря на это, хотя алгоритм и не *, относительно хорошие алгоритмы все еще существуют.Освоение хороших алгоритмов очень помогает нам решать проблемы. В противном случае мы не сможем использовать мудрость наших предшественников и будем вынуждены изучать ее с нуля.Так что же такое хороший алгоритм?
Ну, это так.Некоторые студенты сказали, что хороший алгоритм должен быть как минимум правильным. Если это даже не верно, то какие еще требования?
2.6.1&NBSP; Правильность
Корректность.Корректность алгоритма означает, что алгоритм должен, по крайней мере, иметь однозначные входные, выходные данные и обработку, может правильно отражать потребности проблемы и давать правильный ответ на проблему.
Алгоритм“ правильно”Обычно существуют большие различия в использовании, которые грубо разделены на следующие четыре уровня.
1
2Программа алгоритма может генерировать выходной результат правовых входных данных, которые соответствуют требованиям.
3Программа алгоритма может соответствовать результатам незаконных входных данных для соответствия спецификациям.
4
Для этих четырех уровней значения уровень 1 предъявляет самые низкие требования, но отсутствие грамматических ошибок не является хорошим алгоритмом.Это похоже на простое обеспечение едой и одеждой, что нельзя считать счастливой жизнью.Уровень 4 является самым сложным, и нам практически невозможно проверить, что все входные данные один за другим дают правильные результаты.
Поэтому в большинстве случаев корректность алгоритма доказывается не программами, а математическими методами.Доказать, что сложный алгоритм корректен на всех уровнях, очень дорого.Поэтому обычно мы используем уровень 3 как критерий правильности алгоритма.
Каковы еще характеристики хорошего алгоритма?
Очень хорошо, я слышал, что алгоритм легко понять.Это верно, это все.
2.6.2&NBSP; читаемость
Читаемость: Другая цель дизайна алгоритма - облегчить чтение, понимание и общение.
Высокая читаемость помогает людям понять алгоритм. Неясные алгоритмы часто содержат ошибки, которые трудно обнаружить, отладить и изменить.
Однажды я увидел код, написанный пользователем сети давным-давно. Он заявил, что эта программа“Реализуйте тетрис с наименьшим количеством кода в истории”.“*Меньше кода”Такая крайность делает его код действительно трудным для понимания.Возможно, за исключением компьютера и его самого, большинство людей не могут понять его код.
Цель написания кода, с одной стороны, состоит в том, чтобы позволить компьютеру его выполнить, но другая важная цель — облегчить другим чтение, понимание и общение, и мы также можем прочитать его в будущем. Если читаемость плохая, мы через долгое время не узнаем, что написали.Читабельность — важный показатель качества алгоритма (а также кода, который его реализует).
2.6.3&NBSP; надежность
Хороший алгоритм также должен иметь возможность обрабатывать ситуацию, когда входные данные являются незаконными.Например, время ввода или расстояние не должно быть отрицательным.
Строгость: когда входные данные являются незаконными, алгоритм также может сделать связанную обработку вместо того, чтобы получить ненормальные или необъяснимые результаты.
2.6.4 Высокая эффективность использования времени и малая емкость хранилища
Наконец, хороший алгоритм должен также обладать характеристиками высокой эффективности использования времени и низкой емкости памяти.
求100个人的高考成绩平均分，与求全省的所有考生的成绩平均分在占用时间和内存存储上是有非常大的差异的，我们自然是追求可以高效率和低存储量的算法来解决вопрос.
Таким образом, хороший алгоритм должен обладать характеристиками корректности, читаемости, надежности, высокой эффективности и низкой емкости памяти.
2.7&NBSP; метод измерения эффективности алгоритма
Только что мы упомянули, что алгоритм проектирования должен повысить эффективность.Эффективность здесь в основном относится к времени выполнения алгоритма.Так как же нам измерить время выполнения алгоритма?
Называется“”.
2.7.1&Метод статистики NBSP;
Апостериорный статистический метод: этот метод в основном использует компьютерный таймер для сравнения времени работы программ, скомпилированных с использованием различных алгоритмов, с помощью разработанных тестовых программ и данных, тем самым определяя эффективность алгоритма.
Но этот метод, очевидно, имеет большие недостатки:
«Это должно быть готово заранее в соответствии с алгоритмом, который обычно занимает много времени и энергии.Если он готов найти, что это вообще плохой алгоритм, разве это не бамбуковая корзина, а вода пуста?
«Сравнение времени зависит от факторов окружающей среды, таких как компьютерное оборудование и программное обеспечение, что иногда скрывает преимущества и недостатки самого алгоритма.Вы должны знать, что сегодняшний компьютер с четырехъядерным процессором не может сравниться с компьютерами 286, 386, 486 и других поколений по скорости вычислений алгоритмов обработки; и различия в операционных системах, компиляторах, исполняемых средах и другом используемом программном обеспечении также могут повлиять на их результаты; даже для одной и той же машины различное использование ЦП и памяти приведет к небольшим различиям.
Тестовые данные алгоритма затруднены, и время выполнения программы часто имеет во многом связанном с масштабами тестовых данных. Алгоритм высокой эффективности часто не отражается на небольшой поверхности тестовых данных.Например, сортировка 10 чисел, независимо от того, какие алгоритмы используются, разница почти равна нулю.И если есть миллион случайных сортировки числа, различия в разных алгоритмах очень велики.Таким образом, в качестве алгоритма, сколько данных мы используем для тестирования, трудно судить.
На основе post -after -after -after -after -after - -afters мы не приняты.
2.7.2&NBSP; оцененные методы оценки
Наши компьютерные предшественники изучили метод, называемый оценкой аналогии, чтобы судить об алгоритме.
Метод раннего анализа: до компьютерного программирования алгоритм оценивается на основе статистического метода.
После анализа мы обнаружили, что время, потребляемое программой, написанной на расширенном языке программирования на компьютере, зависит от следующего фактора:
1Стратегия и метод, принятые алгоритмом.
2Качество кода, генерируемого компиляцией.
3Входная шкала проблемы.
4Скорость инструкции по выполнению машины.
Статья 1, конечно, корень алгоритма. Статья 2 должна поддерживаться программным обеспечением, а статья 4 зависит от производительности аппаратного обеспечения.Другими словами, помимо этих факторов, связанных с компьютерным оборудованием и программным обеспечением, время выполнения программы зависит от качества алгоритма и шкалы ввода проблемы.SO -названная шкала ввода проблемы относится к количеству ввода.
Давайте посмотрим на примеры, которые я только что получил в классе сегодня. Два алгоритма для суммирования:
*Алгоритм семян:
int i, sum = 0, n = 100; /* Выполнить 1 время* /
для (i = 1; я<= n; i) /* выполнить n один раз* /
{{
Sum = sum i; /* выполнять n times* /
}
Printf (printf"%d", Сумма); /* Выполнить 1 время* /
Второй алгоритм:
int sum = 0, n = 100; /* Выполнить один раз* /
sum = (1 n) * n/2; /* Выполнить один раз* /
Printf (printf"%d", Сумма); /* Выполнить один раз* /
Очевидно, что алгоритм*типа выполняется 1 (n 1) n один раз = 2n 3 раза; а второй алгоритм составляет 1 1 1 = 3 раза.Фактически,*записи двух алгоритмов совпадают с последним утверждением, поэтому код, на который мы обращаем внимание, на самом деле является средней частью. Мы рассматриваем цикл в целом и игнорируем расходы на суждение головного и хвостового цикла. Затем эти два алгоритма, затем эти два алгоритма на самом деле, это разрыв между n раз и один.Алгоритм очевиден.
Давайте снова продлим приведенный выше пример:
int i, j, x = 0, sum = 0, n = 100; /* Выполнить один раз* /
для (i = 1; я<= n; i)
{{
для (j = 1; j<= n; j)
{{
x ; /*Выполнить n&Раз; n раз*/
sum = sum x;
}
}
Printf (printf"%d", Сумма); /* Выполнить один раз* /
В этом примере у меня есть цикл j петли 100 раз от 1 до 100, и x и sum = sum x в них; фактически, это 1 2 3&Hellip; 10000, то есть в 1002 раза, поэтому в этом алгоритме код круглой части требует общего N2 (игнорирование расходов на велосипедную головку и хвост).Очевидно, что количество выполнения этого алгоритма больше, чем предыдущие два алгоритма для той же шкалы ввода n = 100. Время выполнения этого алгоритма будет гораздо больше, чем предыдущие два с Н.
В настоящее время вы увидите, что надежный метод определения времени выполнения заключается в расчете основной работы базовой работы времени выполнения.Время работы прямо пропорционально этому подсчету.
Нам не волнует, какой язык программирования используется для написания программ, и нам не волнует, на каком компьютере будут участвовать эти программы, мы заботимся только об его алгоритме.Таким образом, операции увеличивающегося и цикла -конца индекса цикла, операция окончания цикла, объявления переменной и результат печати - это операции.*В конце, при анализе времени выполнения программы, Важным является серийные шаги.
Вы можете получить вдохновение из описания проблемы. Входная шкала той же проблемы - n. Ищу*виды алгоритма гармонии, 1 2&Hellip; n требует кода для запуска n раз.Затем входная шкала этой проблемы делает количество операций f (n) = n. Очевидно, что размер того же кода, который работает в 100 раз, в 10 раз больше, чем в 10 раз превышает работу.Второе, независимо от того, сколько N, количество времени работы составляет 1, то есть f (n) = 1; третий тип, в 100 раз в 100 раз в 100 раз превышает работу в 10 раз.Потому что это f (n) = n2.
Когда мы анализируем время выполнения алгоритма, важно связать количество основных операций с входной шкалой, то есть количество основных операций должно быть выражено как функция шкалы ввода (как показано на рисунке 2- 7-1).
Рисунок 2-7-1
Мы можем думать, что по мере того, как значение N становится больше и больше, разница в эффективности времени увеличивается.Например, некоторые из вас учатся каждый день. Я имею в виду полезное обучение, а не только для мертвого чтения экзамена. Каждый день прогрессирует, в то время как другие играют в игры и спят.Все одинаковы при входе в школу, но результаты могут быть очень разными, когда они заканчивают.
2.8&NBSP; постепенный рост функции
Давайте сейчас судим, какой из двух алгоритмов A или B лучше.Предположим, что входная шкала двух алгоритмов составляет n, а алгоритм A должен выполнять операции 2N 3. Вы можете понять, что существует n -времена цикла. После завершения выполнения, есть еще один цикл N, 2N 3 Операции. ПолемАлгоритм B должен выполнять 3N операцию 3n.Как вы думаете, кто они быстрее?
Чтобы быть точным, ответ не обязательно (как показано в таблице 2-8-1).
Таблица 2-8-1
частота
Алгоритм А (2n 3) Алгоритм А’ (2n) алгоритм B (3n 1) алгоритм B’ (3n)
n = 1 5 2 4 3
n = 2 7 7 7 6
n = 3 9 6 10 9
n = 10 23 20 31 30
n = 100 203 200 301 300
Когда n = 1, алгоритм A не так эффективен, как алгоритм B (раз больше, чем алгоритм B).И когда n = 2, они одинаковы; когда n>В 2 часа алгоритм А стал лучше, чем алгоритм B. По мере увеличения n алгоритм A будет лучше и лучше, чем алгоритм B (менее выполненный, чем B).Таким образом, мы можем сделать вывод, что алгоритм А должен быть лучше, чем алгоритм В в целом.
В настоящее время мы даем это определение. В отсутствие входной шкалы n, если в течение всего одного численного N эта функция всегда больше, чем другая функция. Мы называем функцию постепенно растуть.
Постепенный рост функции: дать две функции f (n) и g (n). Если есть целое число n, так что все n>N, f (n) всегда больше, чем g (n), поэтому мы говорим, что рост f (n) становится ближе быстрее, чем g (n).
Из этого мы обнаружили, что с увеличением n последнее 3 на самом деле является изменением алгоритма, которое не влияет на конец, например, алгоритм А″ и алгоритм B″ Итак, мы можем игнорировать эти дополнительные константы.В следующем примере значение такой константы более очевидно.
Давайте посмотрим на второй пример. Алгоритм C составляет 4N 8, а алгоритм D-2n2 1 (как показано в таблице 2-8-2).
Таблица 2-8-2
Алгоритм числа C (4n 8) алгоритм c’ (n) алгоритм D (2n2 1) Алгоритм D’ (n2)
n = 1 12 1 3 1
n = 2 16 2 9 4
n = 3 20 3 19 9
n = 10 48 10 201 100
n = 100 408 100 20 001 10 000
n = 1000 4 008 1 000 2 000 001 000 000 000
Быть н&Во время LE; 3 алгоритм C хуже, чем алгоритм D (потому что алгоритм C чаще), но когда N>После 3 преимущества алгоритма С становятся все лучше и лучше, чем алгоритм D, а позже они намного лучше.Когда более позднее постоянное удаление мы обнаружили, что результаты не изменились.Даже мы даже наблюдали, что даже если постоянная умножается на n, удаляется, этот результат не изменился. Алгоритм C&Количество Prime; с увеличением n, оно намного меньше, чем алгоритм D&Основной;.Другими словами, постоянное умножение*шагов не важно.
Давайте посмотрим на третий пример.Алгоритм E составляет 2n2 3n 1, алгоритм F составляет 2n3 3n 1 (как показано в таблице 2-8-3).
Таблица 2-8-3
Алгоритм числа E (2n2 3n 1) Алгоритм E’ (n2) алгоритм f (2n3 3n 1) алгоритм f’ (n3)
n = 1 616 1
n = 2 15 4 23 8
n = 3 28 9 64 27
n = 10 231 100 2 031 1 000
n = 100 20 301 10 000 2 000 301 1 000 000
Когда n = 1, алгоритм E и алгоритм F имеют одинаковые результаты, но когда n>После 1 преимущества алгоритма E должны быть лучше, чем алгоритм F. По мере увеличения N разница очень очевидна.Установлено, что индекс*шагов велик, и функция будет расти особенно быстрее с ростом Н.
Давайте посмотрим на последний пример.Алгоритм g составляет 2n2, алгоритм h 3n 1, алгоритм I составляет 2n2 3n 1 (как показано в таблице 2-8-4).
Таблица 2-8-4
Алгоритм числа g (2n2) Алгоритм H (3n 1) Алгоритм I (2n2 3n 1)
n = 1 2 4 6
n = 2 8 7 15
n = 5 50 1666
n = 10 200 31 231
n = 100 20000 301 20 301
n = 1000 2 000 000 3 001 2 003 001
n = 10 000 200 000 000 000 000 30 001 200 030 001
n = 100 000 20 000 000 000 000 300 001 20 000 300 001
n = 1000 000 000 000 000 000 000 000 001 001 200 000 3000 001
Этот набор данных должен быть четко виден.Когда значение n становится больше и больше, вы обнаружите, что 3N 1 больше не может сравнить результаты 2N2, и*может почти игнорировать его.Другими словами, поскольку значение n становится очень большим, алгоритм G фактически приближается к алгоритму I.Таким образом, мы можем сделать такой вывод. При оценке эффективности алгоритма постоянные и другие незначительные элементы в функции часто могут быть проигнорированы, и мы должны уделять больше внимания номеру порядка основного пункта (порядок*заказа )
Хорошо судить об алгоритме, мы можем выносить точные суждения только через небольшое количество данных.Согласно нескольким образцам только сейчас, мы обнаружили, что если мы сможем сравнить постепенный рост ключевых функций выполнения этих алгоритмов, мы можем в основном проанализировать: по мере увеличения алгоритма, чем больше, чем другой алгоритм или более и хуже, чем другой алгоритм.Это на самом деле теоретическая основа метода оценки метода заранее, и эффективность времени алгоритма оценивается в результате осложнения времени алгоритма.
2.9 сложности времени алгоритма
2.9.1&NBSP; определение сложности алгоритма времени
В анализе алгоритма общее количество выполнений оператора t (n) является функцией о масштабе n проблемы, а затем анализирует изменение t (n) с изменением n и определяет порядок t (n).Временная сложность алгоритма, то есть количество времени алгоритма, регистрируется как: t (n) = O (f (f (n)).Это означает, что по мере увеличения размера n скорость роста времени выполнения алгоритма совпадает с темпами роста F (n).F (n) является функцией шкалы проблем N.
Таким образом, метод осложнения временной сложности алгоритма используется для отражения временной сложности алгоритма.
При нормальных обстоятельствах, с увеличением n, алгоритм t (n)*медленный - это*превосходный алгоритм.
Очевидно, что определение сложности времени алгоритма можно увидеть, что временная сложность наших трех сумм алгоритмов составляет O (n), O (1) и O (N2).Мы дали им неофициальное имя. O (1) называется постоянным порядком, O (n), называемый линейными шагами, O (n2), называемым квадратными шагами. Конечно, есть и другие шаги, мы представим позже.
2.9.2&NBSP; управляйте методом оценки O -Order
Так как же проанализировать временную сложность алгоритма?То есть, как получить Grand O?Мы даем следующие методы получения, в основном, это пример, который мы приводим.
Управлять классом O:
1. Используйте константу 1, чтобы заменить все дополнительные константы во время выполнения.
2. В модифицированном количестве выполняющих функции сохраняется только элемент*заказа.
3. Если*Заказ существует, а не 1, удалите постоянное умножение с помощью этого элемента.
Результат - Большой О.
Ха, кажется, это игровая стратегия, мы, кажется, получили формулу для производства временной сложности времени для получения алгоритма.Фактически, временная сложность анализа алгоритма не так проста, нам нужно увидеть еще несколько примеров.
2.9.3 постоянный шаг
Прежде всего, временная сложность структуры.Следующий алгоритм - это второй алгоритм (гауссовый алгоритм) только сейчас, почему временная сложность не O (3), а O (1).
int sum = 0, n = 100; /* Выполнить один раз* /
sum = (1 n)*n/2; /* Выполнить один раз* /
Printf (printf"%d", Сумма); /* Выполнить один раз* /
Количество функций выполнения этого алгоритма составляет f (n) = 3.Согласно нашему методу получения класса O,*Шаг - изменить частое число 3 на 1.При сохранении элементов* -заказ обнаружено, что вообще нет элемента заказа, поэтому временная сложность этого алгоритма -O (1).
Кроме того, давайте подумаем об этом, если утверждение в этом алгоритме sum = (1 n)*n/2 имеет 10 предложений, то есть:
int sum = 0, n = 100; /* Выполнить 1 время* /
sum = (1 n)*n/2; /* выполнить первое* /
sum = (1 n)*n/2; /* выполнить 2 -й* / /
sum = (1 n)*n/2; /* выполнить третий раз* /
sum = (1 n)*n/2; /* выполнить четвертый раз* /
sum = (1 n)*n/2; /* выполнить 5th* /
sum = (1 n)*n/2; /* выполнить 6 -е* / /
sum = (1 n)*n/2; /* выполнить 7th* /
sum = (1 n)*n/2; /* выполнить 8th* /
sum = (1 n)*n/2; /* выполнить 9th* /
sum = (1 n)*n/2; /* выполнить 10 -е* / /
Printf (printf"%d", Сумма); /* Выполнить 1 время* /
На самом деле, независимо от того, сколько n на n, эти два раздела - это различия между 3 и 12 выполнением.Это не связано с размером проблемы (сколько из N), и алгоритм постоянного времени выполнения, мы называем это временной сложностью O (1), также называемой постоянным порядком.
Примечание. Независимо от того, насколько это постоянная, мы все помним это как O (1), а не какие -либо другие числа, такие как O (3), O (12). Это ошибка, которую часто совершают новички.
Для структуры ветви, независимо от того, является ли она истинной или ложной, количество выполнения постоянно, и она не будет изменяться в качестве n изменений. Следовательно, степень также является o (1).
2.9.4 линейные шаги
Структура циркуляции линейных шагов будет намного сложнее.Чтобы определить порядок определенного алгоритма, нам часто необходимо определить количество раз, когда конкретный оператор или набор операторов.Поэтому нам необходимо проанализировать сложность алгоритма. Ключом является анализ работы структуры кровообращения.
В следующем коде временная сложность его цикла составляет O (n), потому что код в цикле должен быть выполнен n раз.
int i;
для (i = 0; i<n; я)
{{
/*Последовательность этапа шага сложности времени - O (1)*/
}
2.9.5&NBSP; сочетание
Какова сложность времени следующего кода?
int count = 1;
В то время как (считать<n)
{{
count = count * 2;
/*Последовательность этапа шага сложности времени - O (1)*/
}
Поскольку счет умножен на 2, он ближе к Н.Другими словами, после умножения 2 фаз больше N, цикл будет выходить.Получить x = log2n из 2x = n.Таким образом, временная сложность этого цикла - O (logn).
2.9.6 квадратный шаг
Следующий пример - вложенное круговое. Он только что проанализировал свой внутренний цикл только сейчас, а временная сложность - O (n).
int i, j;
для (i = 0; i<n; я)
{{
для (j = 0; j<n; j)
{{
&Nbsp; /* Последовательность шага программы со сложностью времени o (1)* /
}
}
Для цикла внешнего слоя это только утверждение со сложностью внутреннего времени, а затем циркулирует n раз.Таким образом, временная сложность этого кода составляет O (N2).
Если количество циклов внешнего петля изменяется на M, временная сложность становится O (M M&Раз; n).
int i, j;
для (i = 0; i<м; я)
{{
для (j = 0; j<n; j)
{{
&Nbsp; /* Последовательность шага программы со сложностью времени o (1)* /
}
}
Следовательно, мы можем обобщить, что временная сложность цикла равна сложности тела цикла, умноженного на количество раз времени цикла.
Так в чем же сложности времени вложенного следующего цикла?
int i, j;
для (i = 0; i<n; я)
{{
для (j = i; j<n; j) /* Обратите внимание на int j = i вместо 0* / /
{{
&Nbsp; /* Последовательность шага программы со сложностью времени o (1)* /
}
}
С тех пор, как я = 0, внутренняя циркуляция выполняется n раз. Когда я = 1, выполнять n -1 раза,…… когда я = n -1, внутренний цикл выполняется один раз.Таким образом, общее количество казней
Сущность
Используйте нас, чтобы вывести метод большого O -порядка,*полоса, нет метода добавления метода; второй, только*заказа сохраняются, поэтому n2/2 сохраняется; 1/2,*Сложность времени этого кода является O (N2).
Из этого примера мы также можем получить опыт. Чтобы найти сложность времени для алгоритмов, вам может потребоваться укрепить свою математику, особенно способность к знаниям и проблемы.
Мы продолжаем смотреть на пример, как проанализировать сложность времени вызова метода.
int i, j;
для (i = 0; i<n; я)
{{
функция (i);
}
Приведенный выше код вызывает функцию функции.
void -функция (int count)
{{
Print (count);
}
Функциональное тело печатает этот параметр.На самом деле, это легко понять. Временная сложность функции функции - O (1).Таким образом, общая временная сложность - O (n).
Если функция является следующей:
void -функция (int count)
{{
int j;
для (j = count; j<n; j)
{{
&Nbsp; /* Последовательность шага программы со сложностью времени o (1)* /
}
}
Фактически, это то же самое, что только что упомянутый пример, но внутренняя петля вложенного помещается в функцию, поэтому сложность времени окончания составляет O (N2).
Относительно сложное предложение ниже:
n; /*Количество выполнения составляет 1*/
функция (n); /* Количество выполнений равно n* /
int i, j;
для (i = 0; i<n; я) /* Количество выполнений составляет n2* /
{{
функция (i);
}
для (i = 0; i<n; я) /*Количество выполнения составляет n (n 1)/2*/
{{
для (j = i; j<n; j)
{{
&Nbsp; /* Последовательность шага программы со сложностью времени o (1)* /
}
}
Количество выполнения, в соответствии с методом получения большого O, временная сложность этого кода также составляет O (N2).
2.10&NBSP; общая сложность времени
Общая сложность времени показана в таблице 2-10-1.
Таблица 2-10-1
Выполнить количество функций шага функции
12 O (1) Постоянный шаг
2n 3 O (n) Линейные шаги
3n2 2n 1 O (n2) квадратные шаги
5log2n 20 O (logn) пары цифровых
2n 3nlog2n 19 o (nlogn) nlog2n steps
6n3 2n2 3n 4 o (n3) шаг куба
2n o (2n) Индексные шаги
Время часто используемой сложности времени потребляется от малого до большого ::
Ранее мы упоминали, что O (1) постоянные шаги, O (logn) пары порядка, линейные шаги O (n), квадратные шаги O (n2) и т. Д. Что касается O (nlogn), мы представим в будущих курсах. Как O (N3), слишком большой N сделает результаты нереалистичными.Тот же самый индексный шаг O (2n) и шаг -Уровень O (n!), Если это не маленькое значение N, даже если n -всего 100, это время бега кошмара.Так что эта нереалистичная сложность времени обычно не обсуждается.
2.11 *плохая ситуация и средняя ситуация
После того, как вы выходите на работу утром, вы внезапно вспомнили, что мобильный телефон забыл его принести. Эти годы, ключи, кошельки и мобильные телефоны имеют три основные предметы.Так что иди домой и найди.Когда я открыл дверь, мобильный телефон был на столе крыльца у двери. Оказалось, что когда я вышел, чтобы носить обувь, я забыл ее взять.Это, конечно, лучше, в основном я не трачу время на то, чтобы найти.Но если вы не поместите его туда, вы должны войти, чтобы найти повсюду, найти гостиную, чтобы найти спальню, найти спальню, чтобы найти кухню, и найти кухню, чтобы найти ванную, вы не Это не найдет его. Вы можете использовать мобильный телефон дома и послушать рингтон мобильного телефона. Это действительно глупо.Наконец нашел его под подушкой на кровати.Вы снова идете на работу, поздно.Видя призраков, награду за полную времени в этом году из -за поиска мобильного телефона в Хуанг.
Иногда везет, когда что-то ищешь, а иногда вообще не можешь найти.Но на самом деле обычно подавляющее большинство вещей, с которыми мы сталкиваемся, не являются ни лучшими, ни худшими, поэтому расчет в основном средний.
Анализ алгоритма аналогичен. Мы ищем число в массиве из n случайных чисел. В лучшем случае первое число равно, тогда временная сложность алгоритма равна O(1), но также возможно, что число ожидает в последней позиции, поэтому временная сложность алгоритма равна O(n). Это худший случай.
*Время работы - это гарантия, то есть время работы не будет сломано.В приложениях это важное требование. Как правило, если оно не указано, упомянутое нами время работы - это время выполнения*плохих ситуаций.
Среднее время работы рассчитано с точки зрения вероятности.Возможность этого числа в каждой позиции одинакова, поэтому среднее время поиска составляет n/2 раза, чтобы найти целевой элемент.
Среднее время выполнения является наиболее значимым во всех случаях, поскольку оно является ожидаемым временем выполнения.Другими словами, когда мы запускаем фрагмент программного кода, мы надеемся увидеть среднее время его выполнения.Однако на самом деле среднее время работы трудно получить с помощью анализа. Обычно его оценивают путем анализа определенного количества экспериментальных данных.
Один из способов анализа алгоритма — вычислить среднее значение всех ситуаций. Этот метод расчета временной сложности называется средней временной сложностью.Другой подход заключается в вычислении временной сложности наихудшего случая, которая называется временной сложностью наихудшего случая.Как правило, без специальных указаний речь идет о наихудшей временной сложности.
2.12&NBSP; Сложность пространства алгоритма
Когда мы пишем код, мы можем обменивать пространство на время. Например, чтобы определить, является ли определенный год високосным, вы можете потратить некоторое время на написание алгоритма, а поскольку это алгоритм, это означает, что каждый раз, когда вы указываете год, вам придется вычислять, является ли он високосным.Другой способ — заранее создать массив из 2050 элементов (количество лет немного больше реального), а затем сопоставить все годы с индексными числами.Если это високосный год, значение этого элемента массива равно 1, а если это не високосный год, значение равно 0. Таким образом, так называемая оценка того, является ли определенный год високосным, становится проблемой поиска значения определенного элемента в этом массиве.В это время наша операция сведена к минимуму, но эти 2050 0 и 1 нужно сохранить на жестком диске или в памяти.
Это небольшой трюк, который меняет пространство на время вычислений.Какой из них лучше, на самом деле зависит от того, где вы его используете.
Пространственная сложность алгоритма реализована посредством пространства хранения, требуемого алгоритмом расчета. Формула расчета сложности пространства алгоритма регистрируется как: s (n) = O (f (f (n)). Функция Заявление о пространстве хранения n.
Обычно, когда программа выполняется на машине, помимо хранения инструкций, констант, переменных и входных данных самой программы, ей также необходимо хранить единицы хранения для операций с данными.Если пространство, занимаемое входными данными, зависит только от самой задачи и не имеет никакого отношения к алгоритму, то анализировать нужно только вспомогательные блоки, необходимые для реализации алгоритма.Если вспомогательное пространство, необходимое для выполнения алгоритма, постоянно относительно объема входных данных, говорят, что алгоритм работает на месте, а сложность пространства равна O (1).
Обычно мы все используем&LDQUO; Временная сложность” для обозначения потребностей времени выполнения, использовать&Ldquo; космическая сложность” относится к требованиям к пространству.При использовании без ограниченных слов&Ldquo; сложность&Когда rdquo; обычно обычно относится к сложности времени.Очевидно, что наша книга фокусируется на временной сложности алгоритма.
2.13&NBSP; Сводка обзора
Нелегко, наконец -то снова достиг резюме.
В нашей главе в основном рассказывается о некоторых основных понятиях алгоритма.Говоря о взаимосвязи между структурой данных и алгоритмом неразделима друг от друга.
Определение алгоритма: Алгоритм — это описание шагов по решению конкретной проблемы. В компьютере это конечная последовательность инструкций, и каждая инструкция представляет одну или несколько операций.
Характеристики алгоритмов: конечность, достоверность, осуществимость, вход и выход.
Требования к разработке алгоритма: корректность, читаемость, надежность, высокая эффективность и низкие требования к хранению.
Характеристики алгоритма легко смешиваются с дизайном алгоритма и должны сравнивать память.
Алгоритмические методы измерения: апостериорные статистические методы (ненаучные, неточные), методы предварительного анализа и оценки.
Прежде чем объяснить, как заранее проанализировать метод оценки, мы сначала предоставили определение функции постепенно увеличено.
Постепенный рост функции: дать две функции f (n) и g (n). Если есть целое число n, так что все n>N, f (n) всегда больше, чем g (n), поэтому мы говорим, что рост f (n) становится ближе быстрее, чем g (n).
Затем дайте определение и получите шаги сложности времени алгоритма.
Управлять классом O:
? Замените все аддитивные константы во время выполнения константой 1.
?В измененной функции количества прогонов сохраняется только термин *order.
? Если*Заказы существуют, а не 1, удалите постоянное умножение с помощью этого элемента.
Результат - Большой О.
На этом этапе, после получения количества операций алгоритма, мы можем быстро получить его временную сложность, то есть большую О.В то же время я также напоминаю всем, что на самом деле легко получить Grand O, но как получить выражение количества времени бега, требует математических навыков.
Затем мы дали договоренность о трудоемкой сложности общего времени:
*Позже мы дали концепцию плохой ситуации и средней ситуации алгоритма, а также концепцию сложности пространства.
2.14 заключительное предложение
Многие студенты, изучавшие информатику четыре года, и многие программисты, давно занимающиеся программированием, до сих пор не могут разобраться с оценкой временной сложности алгоритма. Это очень печально.Поскольку я не могу в этом разобраться, я никогда не вникаю в то, является ли написанный мною код неэффективным или можно ли его оптимизировать, чтобы сделать компьютер более быстрым и эффективным.
Их обычное оправдание состоит в том, что сейчас процессоры становятся все быстрее и быстрее, поэтому нет необходимости учитывать качество алгоритма, просто реализуйте функцию, и пользователи не смогут почувствовать скорость, вызванную качеством алгоритма.Но так ли это на самом деле? Давайте позволим данным говорить.
Если предположить, что скорость процессора выросла в 100 раз всего за несколько лет, то на самом деле это преувеличение.И один из наших алгоритмов мог бы написать программу с временной сложностью O(n), но вместо этого написал программу O(n2) только потому, что ее легко придумать и легко написать.То есть по программе алгоритма временной сложности O(n2) скорость на самом деле увеличивается только в 10 раз, а по алгоритму временной сложности O(n) - действительно в 100 раз.
Другими словами, компьютер со старым процессором выполняет программы O(n), а новый процессор, который в 100 раз быстрее, запускает программы O(n2).В конце концов, победителем с высокой эффективностью становится компьютер с центральным процессором старого образца. Причина в том, что качество алгоритма напрямую определяет эффективность работы программы.
Возможно, вы глубоко чувствуете, что перемещение гор Глупым Стариком достойно восхищения, но изобретение пушек и бульдозеров может быть более практичным и умным решением (как показано на рис. 2-14-1).
Рисунок 2-14-1
Я надеюсь, что в своих будущих исследованиях вы будете эффективно использовать инструменты анализа алгоритмов, улучшите свой собственный код и упростите компьютер, так что вы станете даже лучше, чем другие.
……
Эта книга -Ченг Цзе, автор супер -лучшей книги «Модель дизайна Dahua».Принимая обучение учителя компьютера в качестве сцены, чтобы объяснить знание структуры данных и связанных с ними алгоритмов.Вся статья описана в забавном способе, конкурирует большое количество различных жизненных знаний, и полное использование графического языка для отражения абстрактного контента. Для некоторых классических алгоритмов, связанных с сравнением алгоритмов структуры данных.По сравнению с аналогичными книгами по структуре данных на рынке, содержание этой книги весело и легко читается, а объяснение алгоритма подробно и глубоко. Это очень подходящее чтение самоучительного обучения.
В этой книге используется обучение учителя компьютера в качестве сцены для объяснения знаний структуры данных и связанных с ними алгоритмов.Вся статья описана в забавном способе, конкурирует большое количество различных жизненных знаний, и полное использование графического языка для отражения абстрактного контента. Для некоторых классических алгоритмов, связанных с сравнением алгоритмов структуры данных.По сравнению с аналогичными книгами по структуре данных на рынке, содержание этой книги весело и легко читается, а объяснение алгоритма подробно и глубоко. Это очень подходящее чтение самоучительного обучения.
Основное содержание этой книги включает: введение в структуры данных, методы алгоритмического вывода порядка Big O; различия между последовательными структурами и цепочными структурами, применение стеков и очередей;наивное сопоставление строк, алгоритм сопоставления шаблонов KMP; обход двоичного дерева до, в середине и после порядка, деревья Хаффмана и их приложения; обход графов в глубину и вширь; *Два алгоритма для небольших остовных деревьев и два алгоритма для кратчайших путей; топологическая сортировка и алгоритмы критического пути; статические поиски, такие как половинный поиск, поиск с интерполяцией и поиск Фибоначчи; технологии индексирования, такие как плотный индекс, блочный индекс и инвертированный индекс; динамический поиск, такой как дерево двоичной сортировки и сбалансированное двоичное дерево; B-дерево, технология B-дерева, технология хеш-таблиц; простая сортировка, такая как пузырьковая сортировка, выбор, вставка и т. д.; улучшенная сортировка, такая как Хилл, куча, слияние, быстрая и т. д.……
Эта книга подходит для различных читателей, которые выучили язык программирования, в том числе крупные студенты -компьютерные студенты, которые изучают, непрофессиональный персонал, которые хотят переключиться на разработку, свежие или сотрудники, которые хотят протестировать аспирантов, и их нужно пополнить или после работы или необходимо пополнить или после работы. Программисты, которые рассматривают структуру данных и алгоритм и т. Д.
Читатель известен как парень, который очень подходит для написания книг по ИТ -технологиям.Автор "Dahua Design Model".Книга была опубликована 9 раз и напечатана 6 раз в традиционной версии книги в конце 2007 года. Она достигла хороших результатов и создала режим стиля, который подходит для китайцев для чтения.Он участвовал в разработке программного обеспечения и управлении проектами в различных отраслях, таких как правительство, ценные бумаги, игры, транспорт и т. Д., А также выполнял обучения программного обеспечения.Благодаря уникальному опыту обучения математике в старшей школе два с половиной года, а также с точки зрения младших ученых с точки зрения начинающих, он стал одним из популярных авторов ИТ -технологий.