С помощью класса CascadeClassifier , а в частности его метода detectMultiScale() осуществляется поиск лица в кадре. В целом всё устраивает, кроме повышенного потребления вычислительных ресурсов при в общем-то стандартной кадровой частоте в 30 кадров/сек.
Можно было бы попробовать применить cuda::CascadeClassifier , но останавливает соответствующее требование к железу, плюс особое внимание к сборке как OpenCV, так и самого проекта в виду необходимости использования дополнительных библиотек. Метод detectMultiScale() принимает на вход параметры, которыми можно снизить нагрузку.
Например, значения minSize и maxSize ограничивают допустимый размер лица в пикселях. Регулировка этих параметров избавляет алгоритм от необходимости учитывать все возможные вариации размеров, определяемых с шагом scaleFactor . minNeighbors в свою очередь позволяет избавиться от т.н. false positive срабатываний алгоритма, которые чаще всего указывают на область, не являющуюся лицом. Однако всё это во многом сводится на нет, если требуется ловить лицо как вблизи камеры, так и на некотором удалении от оной. То есть в широком диапазоне размеров. В поиске решения пришёл к выводу, что высокое видеоразрешение для детекции лица не требуется. Исходя из этого, написал код, который также может помочь в снижении нагрузки на центральный процессор:
Дела в порядке. Правила личной эффективности. Инесса Аленсон. [Аудиокнига]
// Объект _classifier типа CascadeClassifier // уже загружен соответствующим xml-файлом классификации. // _scale_factor, _min_neighbors, _min_size, _max_size // также инициализируются заранее в качестве атрибутов класса Detector. bool Detector::run(const cv::Mat rects) < if(src_mat.empty() || _classifier.empty()) return false; cv::Mat gry_mat; switch(src_mat.channels()) < case 1: gry_mat = src_mat.clone(); break; case 3: cv::cvtColor(src_mat, gry_mat, cv::COLOR_BGR2GRAY); break; default: return false; >int pyr_cnt = 0; while(gry_mat.cols > 512 || gry_mat.rows > 384) < cv::pyrDown(gry_mat, gry_mat); ++pyr_cnt; >_classifier.detectMultiScale(gry_mat, rects , _scale_factor, _min_neighbors , cv::CASCADE_FIND_BIGGEST_OBJECT , _min_size, _max_size); if(rects.empty()) return true; if(pyr_cnt > 0) < for(int i = 0, n = rects.size(); i < n; ++i) < cv::Rect int cnt = pyr_cnt; while(cnt—) < rc.x *= 2; rc.width *= 2; rc.y *= 2; rc.height *= 2; >> > return true; >
Строка while(gry_mat.cols > 512 || gry_mat.rows > 384) <. >определяет, сколько раз нужно уменьшать кадр в два раза.
В общем-то, это от «балды» и подставить можно любые значения, нежели чем 512х384, например, в зависимости от предполагаемой удалённости объекта от видеокамеры. Функция pyrDown() , уменьшающая кадр ровно в два раза, использована по причине того, что отработает быстрее, нежели чем просто задействовать обычно используемую в подобных случаях cv::resize() . К сожалению, этот подход точно также не решает обозначенную ранее проблему. Если необходимо, чтобы лицо фиксировалось на разных расстояниях, различающихся между собой значительно, то можно переусердствовать с уменьшением кадра и тогда вообще ничего не будет детектироваться. Каким ещё способом можно попытаться решить проблему?
Бизнес-образование: о чем нужно помнить, если хотите построить успешный бизнес
Отслеживать
задан 5 июл 2015 в 16:00
user177227 user177227
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Можно использовать оптический поток. Итеративный алгоритм Лукаса-Канаде работает быстро, а с учётом того, что для задачи трекинга лица не требуется большое количество точек интереса, то скорость обработки каждого кадра будет очень высокой.
Действительно, если лицо обнаружено классификатором каскада, то почему бы далее не использовать возможности трекинга с тем, чтобы отследить местоположение объекта интереса на последующих кадрах. Таким образом, всего лишь совместив детекцию и трекинг, получим значительный прирост в производительности.
Важно учесть один момент: детектор всегда выдаёт прямоугольную область, включающую лицо, но никогда обрамляющую её. Это означает, что прежде чем начать искать точки интереса на области лица, эту самую область необходимо уменьшить с тем, чтобы на фон, который безусловно будет виден в оригинальном прямоугольнике, не попало ни одной точки интереса.
Для устранения препоны можно использовать разные методы, а можно просто уменьшить область интереса, сообразуясь с пропорциями ширины и высоты лица. Собственно, для трекинга будет вполне достаточно использовать небольшого размера прямоугольник, полностью размещающийся внутри области лица:
cv::Rect Tracker::getFaceSubRoi(const cv::Rect cv::rectangle(msk_mat, sub_roi, cv::Scalar(255), -1); // Максимально допустимое кол-во точек интереса. // Сотни штук обычно за глаза. const int max_num_pnts = 100; // Минимально допустимое кол-во точек интереса. const int min_num_pnts = 10; // Находим точки на кадре в области, ограниченной маской. // Прочие параметры устанавливаем по желанию и ситуации. std::vector prv_pnts; cv::goodFeaturesToTrack(gry_mat, prv_pnts, max_num_pnts, 0.001, 5.0, msk_mat, 3); cv::cornerSubPix(gry_mat, prv_pnts, cv::Size(10,10), cv::Size(-1,-1) , cv::TermCriteria(CV_TERMCRIT_ITER|CV_TERMCRIT_EPS,50,0.0001)); // Бывают случаи, когда количество обнаруженных точек меньше допустимого. // Тогда со следующего кадра можно опять начать с детекции. if((int)prv_pnts.size() < min_num_pnts) < /* Ругнуться и выйти */ >// Остаётся построить пирамиду изображений. std::vector prv_pyr; cv::buildOpticalFlowPyramid(gry_mat, prv_pyr, cv::Size(21,21), 3, true , cv::BORDER_REFLECT_101, cv::BORDER_CONSTANT, true);
Теперь имеется всё необходимое, чтобы на следующем кадре производить уже не детекцию, а трекинг.
while(true) < // Читаем кадр в оттенках серого. cv::Mat gry_mat = . // Строим пирамиду изображений для следующего кадра. std::vectornxt_pyr; cv::buildOpticalFlowPyramid(gry_mat, nxt_pyr, cv::Size(21,21), 3, true , cv::BORDER_REFLECT_101, cv::BORDER_CONSTANT, true); // Вычисляем оптический поток, используя «prv_pyr» и «prv_pnts», // полученные ранее. std::vector statuses; std::vector errors; std::vector nxt_pnts; cv::calcOpticalFlowPyrLK(prv_pyr, nxt_pyr, prv_pnts, nxt_pnts , statuses, errors, cv::Size(21,21), 3 , cv::TermCriteria(CV_TERMCRIT_ITER|CV_TERMCRIT_EPS,50,0.0001) , cv::OPTFLOW_LK_GET_MIN_EIGENVALS, 0.0005); // Векторы для хранения смещения каждой из точек интереса по осям. std::vector hrz_offset, vrt_offset; const int n = nxt_pnts.size(); hrz_offset.resize(n); vrt_offset.resize(n); int k = 0; for(int i = 0; i < n; ++i) < if(!statuses.at(i)) continue; const cv::Point2f const cv::Point2f // Если точки вышли за границы области интереса, // то не используем их. if(nxt_pnt.x < sub_roi.x || nxt_pnt.x >sub_roi.br().x) continue; if(nxt_pnt.y < sub_roi.y || nxt_pnt.y >sub_roi.br().y) continue; hrz_offset[k] = nxt_pnt.x-prv_pnt.x; vrt_offset[k] = nxt_pnt.y-prv_pnt.y; nxt_pnts[k++] = nxt_pnt; > nxt_pnts.resize(k); hrz_offset.resize(k); vrt_offset.resize(k); std::swap(prv_pnts, nxt_pnts); std::swap(prv_pyr, nxt_pyr); if((int)prv_pnts.size() < min_num_pnts) < /* Активировать детектор или выполнить поиск точек заново */ continue; >const double const double >
Особенность вышеприведённого цикла for(int i = 0; i < n; ++i) <. >в том, что он отсеивает те точки интереса, которые в силу различных условий перестали быть актуальными. Например по той причине, что алгоритм Лукаса-Канаде для каких-либо из них не смог провести соответствия между предыдущим и следующим кадром. Постепенно количество ранее обнаруженных точек будет уменьшаться и когда достигнет минимального значения min_num_pnts потребуется снова активировать детектор или выполнить поиск точек интереса заново.
Под конец цикла while(true) <. >вызывается функция calculateAverageOffset() , которая может просто вычислять среднее значение вектора, поданного ей на вход, либо, например, по пику в распределении Гаусса брать из вектора определённое значение.
Рассмотренный код функционирует на порядок быстрее, нежели если производить детекцию лица на каждом кадре. Однако у него имеются и отрицательные стороны. Голова — это трёхмерный объект, а значит сильные повороты и наклоны могут приводить к не вполне ожидаемым результатам. Также необходимо помнить о том, что оптический поток плохо работает на смещениях, скорость которых слишком высока по отношению к скорости видеозахвата. Иными словами, если объект будет резко мотать головой при стандартных 30 кадрах/сек, то трекинг собъётся и результат окажется неприемлемым.
Напоследок хочется добавить, что подход вовсе не ограничен применением одного только Лукаса-Канаде. Он в той же мере может быть использован, например, с алгоритмом Фарнебэка, реализация которого в OpenCV также имеется. Или, например, можно использовать трекинг по корреляции фазы, вопреки её традиционному использованию в основном в задачах стабилизации видео.
Источник: ru.stackoverflow.com
Сноски. 6 класс _сноски_КСП надомник. Разработка и трассировка алгоритма
Единственный в мире Музей Смайликов
Самая яркая достопримечательность Крыма
Скачать 22.85 Kb.
| Раздел: | Программирование алгоритмов на языке программироания Python (пайтон) | |
| Школа: | ||
Мозговой штурм
От чего зависит эффективность алгоритма?
Сделать вывод, что эффективнее алгоритм тот, который использует меньшее количества ресурсов.
(с помощью видеозаписи теоретический и практический материал)
Работа в группах
Изучите статью об эффективности алгоритма (см.ресурсы, дидактический материал). Обсудите в паре и подготовьте постер по вопросам:
— Потребление каких ресурсов может быть уменьшено?
— Как оценить сложность алгоритма?
— Потребление каких ресурсов может быть уменьшено в вашем алгоритме, а в дальнейшем и в программе? Какие изменения в своем алгоритме вы предполагаете сделать?
- Афиширование работы групп
- Улучшение собственного алгоритма
(с помощью видеозаписи)
Отвечают на вопросы
Отвечает на вопрос для чего нужна сноска в документах — 1 балл
Отвечает на вопрос Каких видов бывают сноски? И чем они отличаются друг от друга? -1 балл
Отвечает на вопрос как удалить сноску?
Использует свой текст и добавляет простую сноску – 2 балла
Использует свой текст и добавляет концевую сноску – 2 балла
Комментарии при формативном оценивании в кунделике, общий комментарий в предметной группе в Группа WhatsApp
Все учащиеся задают вопросы в кунделике или в группе WhatsApp
Источник: topuch.com
Анализ сложности алгоритмов. Примеры
Алгоритм — это точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату [1].
При разработке алгоритмов очень важно иметь возможность оценить ресурсы, необходимые для проведения вычислений, результатом оценки является функция сложности (трудоемкости). Оцениваемым ресурсом чаще всего является процессорное время (вычислительная сложность) и память (сложность алгоритма по памяти). Оценка позволяет предсказать время выполнения и сравнивать эффективность алгоритмов.
Содержание:
- Модель RAM (Random Access Machine)
- Подсчет операций. Классы входных данных
- Асимптотические обозначения
- Примеры анализа алгоритмов
- Математический аппарат анализа алгоритмов
- Формулы суммирования
- Суммирование и интегрирование
- Сравнение сложности алгоритмов. Пределы
- Логарифмы и сложность алгоритмов
Модель RAM (Random Access Machine)
- память состоит из ячеек, каждая из которых имеет адрес и может хранить один элемент данных;
- каждое обращение к памяти занимает одну единицу времени, независимо от номера адресуемой ячейки;
- количество памяти достаточно для выполнения любого алгоритма;
- процессор выполняет любую элементарную операцию (основные логические и арифметические операции, чтение из памяти, запись в память, вызов подпрограммы и т.п.) за один временной шаг;
- циклы и функции не считаются элементарными операциями.
Несмотря на то, что такая модель далека от реального компьютера, она замечательно подходит для анализа алгоритмов. После того, как алгоритм будет реализован для конкретной ЭВМ, вы можете заняться профилированием и низкоуровневой оптимизацией, но это будет уже оптимизация кода, а не алгоритма.
Подсчет операций. Классы входных данных
Одним из способов оценки трудоемкости ((T_n)) является подсчет количества выполняемых операций. Рассмотрим в качестве примера алгоритм поиска минимального элемента массива.
начало; поиск минимального элемента массива array из N элементов min := array[1] для i от 2 до N выполнять: если array[i] < min min := array[i] конец; вернуть min
При выполнении этого алгоритма будет выполнена:
- N — 1 операция присваивания счетчику цикла i нового значения;
- N — 1 операция сравнения счетчика со значением N;
- N — 1 операция сравнения элемента массива со значением min;
- от 1 до N операций присваивания значения переменной min.
Точное количество операций будет зависеть от обрабатываемых данных, поэтому имеет смысл говорить о наилучшем, наихудшем и среднем случаях. При этом худшему случаю всегда уделяется особое внимание, в том числе потому, что «плохие» данные могут быть намеренно поданы на вход злоумышленником.
Понятие среднего случая используется для оценки поведения алгоритма с расчетом на то, что наборы данных равновероятны. Однако, такая оценка достаточно сложна:
- исходные данные разбиваются на группы так, что трудоемкость алгоритма ((t_i)) для любого набора данных одной группы одинакова;
- исходя из доли наборов данных группы в общем числе наборов, рассчитывается вероятность для каждой группы ((p_i));
- оценка среднего случая вычисляется по формуле: (sumlimits_^m p_icdot t_i).
Асимптотические обозначения
Подсчет количества операций позволяет сравнить эффективность алгоритмов. Однако, аналогичный результат можно получить более простым путем. Анализ проводят с расчетом на достаточно большой объем обрабатываемых данных (( n to infty )), поэтому ключевое значение имеет скорость роста функции сложности, а не точное количество операций.
При анализе скорости роста игнорируются постоянные члены и множители в выражении, т.е. функции (f_x = 10 cdot x^2 + 20 ) и ( g_x = x^2) эквивалентны с точки зрения скорости роста. Незначащие члены лишь добавляют «волнистости», которая затрудняет анализ.
В оценке алгоритмов используются специальные асимптотические обозначения, задающие следующие классы функций:
- (mathcal(g)) — функции, растущие медленнее чем g;
- (Omega(g)) — функции, растущие быстрее чем g;
- (Theta(g)) — функции, растущие с той же скоростью, что и g.
Запись (f_n = mathcal(g_n)) означает принадлежность функции f классу (mathcal(g)), т.е. функция f ограничена сверху функцией g для достаточно больших значений аргумента. (exists n_0 > 0, c > 0 : forall n > n_0, f_n leq c cdot g_n).
Ограниченность функции g снизу функцией f записывается следующим образом: (g_n =Omega(f_n)). Нотации (Omega) и (mathcal) взаимозаменяемы: (f_n = mathcal(g_n) Leftrightarrow g_n =Omega(f_n)).
Если функции f и g имеют одинаковую скорость роста ((f_n = Theta(g_n))), то существуют положительные константы (c_1) и (c_2) такие, что (exists n_0 > 0 : forall n > n_0, f_n leq c_1 cdot g_n, f_n geq c_2 cdot g_n). При этом (f_n = Theta(g_n) Leftrightarrow g_n = Theta(f_n)).
Примеры анализа алгоритмов
Алгоритм поиска минимального элемента массива, приведенный выше, выполнит N итераций цикла. Трудоемкость каждой итерации не зависит от количества элементов массива, поэтому имеет сложность (T^ = mathcal(1)). В связи с этим, верхняя оценка всего алгоритма (T^_n = mathcal(n) cdot mathcal(1) = mathcal(n cdot 1) = mathcal(n)). Аналогично вычисляется нижняя оценка сложности, а в силу того, что она совпадает с верхней — можно утверждать (T^_n = Theta(n) ).
Алгоритм пузырьковой сортировки (bubble sort) использует два вложенных цикла. Во внутреннем последовательно сравниваются пары элементов и если оказывается, что элементы стоят в неправильном порядке — выполняется перестановка. Внешний цикл выполняется до тех пор, пока в массиве найдется хоть одна пара элементов, нарушающих требуемый порядок [2].
начало; пузырьковая сортировка массива array из N элементов nPairs := N; количество пар элементов hasSwapped := false; пока что ни одна пара не нарушила порядок для всех i от 1 до nPairs-1 выполнять: если array[i] > array[i+1] то: swap(array[i], array[i+1]); обменять элементы местами hasSwapped := true; найдена перестановка nPairs := nPairs — 1; наибольший элемент гарантированно помещен в конец если hasSwapped = true — то перейти на п.3 конец; массив array отсортирован
Трудоемкость функции swap не зависит от количества элементов в массиве, поэтому оценивается как (T^ = Theta(1) ). В результате выполнения внутреннего цикла, наибольший элемент смещается в конец массива неупорядоченной части, поэтому через N таких вызовов массив в любом случае окажется отсортирован. Если же массив отсортирован, то внутренний цикл будет выполнен лишь один раз.
- (T^_n = mathcal(sumlimits_^n sumlimits_^ 1) = mathcal(sumlimits_^n n) = mathcal(n ^2));
- (T^_n = Omega(1 cdot sumlimits_^ 1) = Omega(n)).
В алгоритме сортировки выбором массив мысленно разделяется на упорядоченную и необработанную части. На каждом шаге из неупорядоченной части массива выбирается минимальный элемент и добавляется в отсортированную часть [2].
начало; selection_sort — сортировка массива array из N элементов методом выбора для всех i от 1 до N выполнять: imin := indMin(array, N, i) swap(array[i], array[imin]) конец; массив array отсортирован
Для поиска наименьшего элемента неупорядоченной части массива используется функция indMin, принимающая массив, размер массива и номер позиции, начиная с которой нужно производить поиск. Анализ сложности этой функции можно выполнить аналогично тому, как это сделано для функции min — количество операций линейно зависит от количества обрабатываемых элементов: ( T^_ = Theta(n — i)).
У сортировки выбором нет ветвлений, которые могут внести различия в оценку наилучшего и наихудшего случаев, ее трудоемкость: (T^_n = Theta(sumlimits_^ (T^_ + T^)) =Theta(sumlimits_^ (n-i)) = Theta(frac cdot n) = Theta(n^2) ).
Математический аппарат анализа алгоритмов
Выше были рассмотрены асимптотические обозначения, используемые при анализе скорости роста. Они позволяют существенно упростить задачу отбросив значительную часть выражения. Однако, в математическом анализе имеется целый ворох таких приемов.
Формулы суммирования
В примерах, рассмотренных выше, мы уже сталкивались с нетривиальными формулами суммирования. Чтобы дать оценку суммы можно использовать ряд известных тождеств:
- вынос постоянного множителя за знак суммы: (sumlimits_^ (c cdot f_i) = c cdot sumlimits_^ cdot f_i);
- упрощение суммы составного выражения: (sumlimits_^ (f_i + g_i) = sumlimits_^ (f_i) + sumlimits_^ (g_i));
- сумма чисел арифметической прогрессии: (sumlimits_^ (i^p) = Theta(n^));
- сумма чисел геометрической прогрессии: (sumlimits_^ (a^i) = frac — 1)>). При ( n to infty ) возможны 2 варианта:
- если a < 1, то сумма стремится к константе: (Theta(1));
- если a > 1, то сумма стремится к бесконечности: (Theta(a^));
- если a = 0, формула неприменима, сумма стремится к N: (Theta(n));
Первые из этих тождеств достаточно просты, их можно вывести используя метод математической индукции. Если под знаком суммы стоит более сложная формула, как в двух последних тождествах — суммирование можно заменить интегрированием (взять интеграл функции гораздо проще, ведь для этого существует широкий спектр приемов).
Суммирование и интегрирование
Известно, что интеграл можно понимать как площадь фигуры, размещенной под графиком функции. Существует ряд методов аппроксимации (приближенного вычисления) интеграла, к ним относится, в частности, метод прямоугольников. Площадь под графиком делится на множество прямоугольников и приближенно вычисляется как сумма их площадей. Следовательно, возможен переход от интеграла к сумме и наоборот.
аппроксимация интеграла левыми прямоугольниками
аппроксимация интеграла правыми прямоугольниками
На рисунках приведен пример аппроксимации функции (f_x = log x) левыми и правыми прямоугольниками. Очевидно, они дадут верхнюю и нижнюю оценку площади под графиком:
- (intlimits_a^n f_x dx leq sumlimits_^ f_i leq intlimits_^ f_x dx) для возрастающих функций;
- (intlimits_a^n f_x dx geq sumlimits_^ f_i geq intlimits_^ f_x dx) для убывающих функций.
В частности, такой метод позволяет оценить алгоритмы, имеющие логарифмическую сложность (две последние формулы суммирования).
Сравнение сложности алгоритмов. Пределы
Сложность алгоритмов определяется для больших объемов обрабатываемых данных, т.е. при (ntoinfty). В связи с этим, при сравнении трудоемкости двух алгоритмов можно рассмотреть предел отношения функций их сложности: (limlimits_ frac ). В зависимости от значения предела возможно сделать вывод относительно скоростей роста функций:
- предел равен константе и не равен нулю, значит функции растут с одной скоростью:(f_n = Theta(g_n));
- предел равен нулю, следовательно (g_n) растет быстрее чем (f_n): (f_n = mathcal(g_n));
- предел равен бесконечности, (g_n) растет медленнее чем (f_n): (f_n = Omega(g_n)).
Если функции достаточно сложны, то такой прием значительно упрощает задачу, т.к. вместо предела отношения функций можно анализировать предел отношения их производных (согласно правилу Лопиталя): (limlimits_ frac = limlimits_ frac ). Правило Лопиталя можно использовать если функции обладают следующими свойствами:
- (limlimits_ frac = fracили frac <infty><infty>);
- ( f_n ) и (g_n) дифференцируемы;
- ( g’_n ne 0 ) при (n to infty);
- (exists limlimits_ frac ).
Допустим, требуется сравнить эффективность двух алгоритмов с оценками сложности (mathcal(a^n)) и (mathcal(n^b)), где a и b — константы. Известно, что ((c^x)’ =c^x cdot ln(c)), но ((x^c)’ = c cdot x^ ). Применим правило Лопиталя к пределу отношения наших функций b раз, получим: (limlimits_ frac <mathcal(a^n)><mathcal(n^b)> = limlimits_ frac <mathcal(a^n * ln^b (a))><mathcal(b!)> = infty). Значит функция (a^n) имеет более высокую скорость роста. Без использования пределов и правила Лопиталя такой вывод может казаться не очевидным.
Логарифмы и сложность алгоритмов. Пример
По определению (log_a = b Leftrightarrow x = a^b). Необходимо знать, что (x to infty Rightarrow log_a to infty), однако, логарифм — это очень медленно растущая функция. Существует ряд формул, позволяющих упрощать выражения с логарифмами:
- (log_a = log_a + log_a< y>);
- (log_a = b cdot log_a< x>);
- (log_a =frac<log_b><log_b>).
При анализе алгоритмов обычно встречаются логарифмы по основанию 2, однако основание не играет большой роли, поэтому зачастую не указывается. Последняя формула позволяет заменить основание логарифма, домножив его на константу, но константы отбрасываются при асимптотическом анализе.
Логарифмической сложностью обладают алгоритмы, для которых не требуется обрабатывать все исходные данные, они используют принцип «разделяй и властвуй». На каждом шаге часть данных (обычно половина) отбрасывается. Примером может быть функция поиска элемента в отсортированном массиве (двоичного поиска):
начало; поиск элемента E в отсортированном по возрастанию массиве array из N элементов left := 1, right := N; левая и правая граница, в которых находится искомый элемент выполнять пока left =< right: mid := (right + left) div 2; вычисление индекса элемента посередине рассматриваемой части массива если array[mid] = E конец; вернуть true (элемент найден) если array[mid] < E; искомый элемент больше середины, значит все элементы левее mid можно отбросить left := mid + 1; иначе right := mid конец; вернуть false (элемент не найден)
Очевидно, что на каждом шаге алгоритма количество рассматриваемых элементов сокращается в 2 раза. Количество элементов, среди которых может находиться искомый, на k-том шаге определяется формулой (frac). В худшем случае поиск будет продолжаться пока в массиве не останется один элемент, т.е. чтобы определить количество итераций для верхней оценки, достаточно решить уравнение (1 = frac Rightarrow 2^i = n Rightarrow i = log_2 n). Следовательно, алгоритм имеет логарифмическую сложность: (T^_n = mathcal(log n)).
Результаты анализа. Замечания. Литература
Оценка сложности — замечательный способ не только сравнения алгоритмов, но и прогнозирования времени их работы. Никакие тесты производительности не дадут такой информации, т.к. зависят от особенностей конкретного компьютера и обрабатывают конкретные данные (не обязательно худший случай).
Анализ алгоритмов позволяет определить минимально возможную трудоемкость, например:
- алгоритм поиска элемента в неупорядоченном массиве не может иметь верхнюю оценку сложности лучше, чем (mathcal(n)). Это связано с тем, что невозможно определить отсутствие элемента в массиве (худший случай) не просмотрев все его элементы;
- возможно формально доказать, что не возможен алгоритм сортировки произвольного массива, работающий лучше чем (mathcal(n cdot log n)) [5].
Нередко на собеседованиях просят разработать алгоритм с лучшей оценкой, чем возможно. Сами задачи при этом сводятся к какому-либо стандартному алгоритму. Человек, не знакомый с асимптотическим анализом начнет писать код, но требуется лишь обосновать невозможность существования такого алгоритма.
- Васильев В. С. Алгоритм. Свойства алгоритма [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/578. Дата обращения: 06.01.2014.
- Васильев В. С. Блок-схемы алгоритмов сортировки пузырьком, выбором и вставками [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/1462. Дата обращения: 06.01.2014.
- Дж. Макконелл Анализ алгоритмов. Активный обучающий подход. — 3-е дополненное издание. М: Техносфера, 2009. -416с.
- Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер ; пер. с англ. — М. : БИНОМ. Лаборатория знаний, 2006. — 406 с.
- Скиена С. Алгоритмы. Руководство по разработке. 2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург. 2011. — 720 с.: ил.
Источник: pro-prof.com