Мера использования алгоритмом ресурсов времени или пространства




НазваниеМера использования алгоритмом ресурсов времени или пространства
Дата конвертации23.07.2013
Размер445 b.
ТипПрезентации



Введение

  • Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов (например, алгоритмов поиска и сортировки), чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа.



мера использования алгоритмом ресурсов времени или пространства.

  • мера использования алгоритмом ресурсов времени или пространства.



F (n) – функция трудоемкости, определяющая зависимость между входными данными и кол-вом базовых операций ( временными затратами алгоритма )

  • F (n) – функция трудоемкости, определяющая зависимость между входными данными и кол-вом базовых операций ( временными затратами алгоритма )



множества вычислительных проблем, для решения которых известны алгоритмы, схожие по сложности

  • множества вычислительных проблем, для решения которых известны алгоритмы, схожие по сложности



Проблемы, решение которых считается «быстрым», то есть полиноминально зависящим от размера входных данных (например, O(n), O(n2))

  • Проблемы, решение которых считается «быстрым», то есть полиноминально зависящим от размера входных данных (например, O(n), O(n2))



Проблемы, для решения которых используются лишь алгоритмы, экспоненциально зависящие от размера входных данных (например, O(2n))

  • Проблемы, для решения которых используются лишь алгоритмы, экспоненциально зависящие от размера входных данных (например, O(2n))







- алгоритм нахождения заданного значения произвольной функции в некотором наборе значений

  • - алгоритм нахождения заданного значения произвольной функции в некотором наборе значений



- простейший вид поиска заданного элемента на некотором отрезке (множестве), осуществляемый путем последовательного сравнения очередного рассматриваемого значения с искомым до тех пор, пока эти значения не совпадут

  • - простейший вид поиска заданного элемента на некотором отрезке (множестве), осуществляемый путем последовательного сравнения очередного рассматриваемого значения с искомым до тех пор, пока эти значения не совпадут



Если отрезок имеет длину n, то найти решение с точностью до ε можно за время n/ ε

  • Если отрезок имеет длину n, то найти решение с точностью до ε можно за время n/ ε



template

  • template

  • int linear_search(const vector& v, const T& item)

  • {

  • for (int i = 0; i < v.size(); i++)

  • {

  • if (v[i] == item)

  • {

  • return i; // элемент найден

  • }

  • }

  • return -1; // элемент не найден

  • }



За:

  • За:

  • Не требует сортировки значений множества

  • Не требует дополнительного анализа функции.

  • Не требует дополнительной памяти.

  • => Следовательно, может работать в потоковом режиме при непосредственном получении данных из любого источника.



- поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Поиск заканчивается при совпадении искомого элемента с элементом- границей между частями множества или при отсутствии искомого элемента.

  • - поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Поиск заканчивается при совпадении искомого элемента с элементом- границей между частями множества или при отсутствии искомого элемента.



Упорядоченное по возрастанию множество элементов, необходимо найти элемент с значением, равным 9

  • Упорядоченное по возрастанию множество элементов, необходимо найти элемент с значением, равным 9





template

  • template

  • int binary_search(const vector& v, const T& item) {

  • int low = 0;

  • int high = v.size() - 1;

  • int mid;

  • while (low <= high) { // нахождение элемента-границы

  • mid = (low + high) / 2;

  • If (v[mid] < item) {

  • low = mid + 1;} // обращаемся выше элемента-границы

  • else if (v[mid] > item) {

  • high = mid - 1; // обращаемся ниже элемента-границы

  • }else { //элемент найден

  • return mid;}}

  • return -1; // элемент не найден

  • }



Когда функция имеет вещественный аргумент, найти решение с точностью до ε можно за время (log a), где a=1/ε. Когда аргумент дискретен, и изначально лежит на отрезке длины n, поиск решения займёт (1+ log n) времени

  • Когда функция имеет вещественный аргумент, найти решение с точностью до ε можно за время (log a), где a=1/ε. Когда аргумент дискретен, и изначально лежит на отрезке длины n, поиск решения займёт (1+ log n) времени



За:

  • За:

  • Относительная быстрота выполнения поиска (по линейным)



- алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. Остальные поля могут в ней не участвовать.

  • - алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. Остальные поля могут в ней не участвовать.



Устойчивость – изменение относительного положения равных элементов

  • Устойчивость – изменение относительного положения равных элементов

  • Естественность поведения – улучшение работы алгоритма при улучшении (частичной или полной сортировке) входных данных

  • Сравнения - количество операций сравнения элементов

  • Перестановки - количество перестановок элементов



алгоритм сортировки массива целых положительных чисел, лежащих в определённом диапазоне. При выполнении этого алгоритма подсчитывается число элементов, меньших текущего элемента х, и число одинаковых элементов, а затем выстраивается новый массив, в который элемент х записывается сразу «на свое место» (исходя из этих подсчётов)

  • алгоритм сортировки массива целых положительных чисел, лежащих в определённом диапазоне. При выполнении этого алгоритма подсчитывается число элементов, меньших текущего элемента х, и число одинаковых элементов, а затем выстраивается новый массив, в который элемент х записывается сразу «на свое место» (исходя из этих подсчётов)



// A[1..n] – входной массив, B[1..n] – выходной, C[1..k] -

  • // A[1..n] – входной массив, B[1..n] – выходной, C[1..k] -

  • // вспомогательный, k- максимальное число элементов в массиве A

  • for i := 1 to k

  • do C[i] := 0

  • for j :=1 to length[A]

  • do C[A[j]] := C[A[j]]+ 1

  • C[i] равно количеству элементов, равных i

  • for i := 2 to k

  • do C[i] := C[i] + C[i -1]

  • C[i] равно количеству элементов, не превосходящих i

  • for j := length[A] downto 1

  • do B[C[A[j]]] := A[j]

  • C[A[j]] := C[A[j]]-1



Циклы в строках 1-2 и 6-7 работают за время O(k),

  • Циклы в строках 1-2 и 6-7 работают за время O(k),

  • Циклы в строках 3-4 и 10-11 - за время O(n),

  • Значит, весь алгоритм работает за время O(n+k); если k= O(n), то время работы (временная сложность) есть O(n)



За:

  • За:

  • Устойчивая сортировка: если во входном массиве присутствуют несколько одинаковых чисел, то в выходном массиве они стоят в том же порядке, что и во входном



- неустойчивый алгоритм сортировки, при котором выбирается минимальное значение, производится обмен этого значения со значением на первой позиции в списке (массиве, множестве). Эти операции повторяются с хвостом списка: исключаются уже отсортированные элементы – до тех пор, пока весь список не будет отсортирован.

  • - неустойчивый алгоритм сортировки, при котором выбирается минимальное значение, производится обмен этого значения со значением на первой позиции в списке (массиве, множестве). Эти операции повторяются с хвостом списка: исключаются уже отсортированные элементы – до тех пор, пока весь список не будет отсортирован.



1.Начальный массив

  • 1.Начальный массив

  • 2.Минимальный элемент = 12

  • 3. Минимальный элемент = 7

  • 4…. Минимальный элемент = 3

  • Затем повторяются те же шаги

  • без учёта отсортированного

  • элемента

  • 5. Итог – отсортированный массив



template

  • template

  • void selection_sort(vector& v) {

  • for (int i = 0; i < v.size() - 1; i++) {

  • int best = i;

  • for (int j = i + 1; j < v.size(); j++) {

  • if (v[j] < v[best]) {

  • best = j;

  • }

  • }

  • if (best != i) {

  • T temp = v[i];

  • v[i] = v[best];

  • v[best] = temp;

  • }

  • }

  • }



На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае O(n2), предполагая что сравнения делаются за постоянное время.

  • На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае O(n2), предполагая что сравнения делаются за постоянное время.



Алгоритм быстрой сортировки

  • алгоритм сортировки списка (множества, массива), основанный на принципе «разделяй и властвуй», самый быстрый из известных универсальных алгоритмов сортировки.



Алгоритм быстрой сортировки

  • Выбираем в массиве некоторый элемент, который будем называть опорным элементом;

  • Разделяем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него;

  • Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента;

  • Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов.



Сложность алгоритма быстрой сортировки

  • Лучший случай: O (n log n);

  • Промежуточный случай: O (n log n);

  • Худший случай: O (n2);



Достоинства:

  • Достоинства:

  • Самый быстродействующий из всех существующих неспециализированных алгоритмов обменной сортировки;

  • Простая реализация;

  • Хорошо сочетается с алгоритмами кэширования и подкачки памяти;

  • Хорошо работает на «почти отсортированных» (естественность поведения)



Москва, 2008

  • Москва, 2008



Похожие:

Мера использования алгоритмом ресурсов времени или пространства iconНалогообложение использования природных ресурсов. Платежи за природные ресурсы
Право пользования и использования природных ресурсов в пределах установленных лимитов
Мера использования алгоритмом ресурсов времени или пространства iconОхарактеризовать основные виды природных ресурсов. Оценить размещение природных ресурсов и масштабы их использования
Это компоненты природы, которые человек использует или может использовать в хозяйственной деятельности
Мера использования алгоритмом ресурсов времени или пространства iconЛекция №13 управление задачами в операционных системах учебные вопросы
Основным подходом в организации того или иного метода управления процессами, обеспечивающего эффективную загрузку ресурсов или выполнение...
Мера использования алгоритмом ресурсов времени или пространства iconПлан лекции Договоримся о терминах и определениях Среда ит и среды их применения Распределение цифрового пространства 10 перспективных ит по мнению Gartner на 2010 год
«Предоставление вычислительных ресурсов на необходимом уровне в режиме реального времени», из одной диссертации 1984 года
Мера использования алгоритмом ресурсов времени или пространства iconВселенная — обычно определяется как совокупность всего, что существует физически. Это совокупность пространства и времени, всех форм материи, физических законов и констант.
Это совокупность пространства и времени, всех форм материи, физических законов и констант. Однако термин "Вселенная " может трактоваться...
Мера использования алгоритмом ресурсов времени или пространства iconИспользование и эксплуатация информационных систем
...
Мера использования алгоритмом ресурсов времени или пространства iconЛекция 8 Экономические инструменты стимулирования природоохранной деятельности Инструменты Плата за загрязнение Ценовая политика Финансово-кредитный механизм
Система стимулирования охраны природы и рационального использования природных ресурсов предполагает повышение заинтересованности...
Мера использования алгоритмом ресурсов времени или пространства iconГрадусная мера дуги окружности Геометрия 8 класс 12. 04. 2011 г. Дуга окружности
О меньше полуокружности или является полуокружностью, то ее градусная мера считается равной градусной мере центрального угла
Мера использования алгоритмом ресурсов времени или пространства iconСтратегия эффективного использования древесного топлива в Швеции Доцент, к т. н. Т. Штерн
Политические решения, доступность ресурсов, технологические достижения и экономика определяют темпы роста использования возобновляемых...
Мера использования алгоритмом ресурсов времени или пространства iconЛекция №1 Введение в компьютерные сети. История и эволюция. Основные понятия
Компьютерная сеть совокупность из нескольких компьютеров (вычислителей), объединённых посредством телекоммуникаций для обеспечения...
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница