Что означает следующая фраза алгоритм x асимптотически более эффективен чем y
Алгоритм — тест с ответами
Информатика в настоящее время является стремительно развивающийся наукой. Многие студенты постают в технические университеты, чтобы в будущем связать свою деятельность с IT или приближенными областями. Для проверки знаний по теме Алгоритм предлагаем пройти тестирование на этой странице. Обращаем ваше внимание, что в тесте правильные ответы выделены символом [+].
Что называется алгоритмом:
[-] а) протокол вычислительной сети
[+] б) описание последовательности действий, строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов
[-] в) правила выполнения определенных действий
Линейным называется алгоритм, если:
[+] а) его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий
[-] б) он включает в себя вспомогательный алгоритм
[-] в) он представим в табличной форме
Цикличным называется алгоритм, если:
[-] а) он представим в табличной форме
[-] б) ход его выполнения зависит от истинности тех или иных условий
[+] в) он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий
Алгоритм включает в себя ветвление, если:
[+] а) ход его выполнения зависит от истинности тех или иных условий
[-] б) он включает в себя вспомогательный алгоритм
[-] в) он представим в табличной форме
Что является свойством алгоритма:
[-] б) простота записи на языках программирования
Как называется свойство алгоритма, заключающееся в том, что каждое действие и алгоритм в целом должны иметь возможность завершения:
Как называется свойство алгоритма, заключающееся в том, что алгоритм должен состоять из конкретных действий, следующих в определенном порядке:
Как называется свойство алгоритма, заключающееся в отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях:
Как называется свойство алгоритма, заключающееся в том, что один и тот же алгоритм можно использовать с разными исходными данными:
Как называется свойство алгоритма, заключающееся в том, что любое действие должно быть строго и недвусмысленно определено в каждом случае:
Как называется алгоритм, записанный на “понятном” компьютеру языке программирования:
[-] в) протокол алгоритма
Для того, чтобы алгоритм бинарного поиска работал правильно нужно, чтобы список был:
[-] б) выходящим из стека
Необходимо определить максимальное количество узлов в двоичном дереве с высотой k, где корень — нулевая высота:
Укажите обозначение следующей фразы: “алгоритм X асимптотически более эффективен, чем Y”:
[-] а) X будет лучшим выбором для всех входов
[-] б) X будет лучшим выбором для всех входов, кроме больших входов
[+] в) X будет лучшим выбором для всех входов, за исключением, возможно, небольших входов
Чем отличается алгоритм обхода графа от алгоритма обхода вершин дерева:
[+] а) графы могут иметь циклы
[-] б) у деревьев есть корни
[-] в) деревья не соединяются
Какой из алгоритмов, перечисленных ниже, будет самым производительным, если дан уже отсортированный массив:
[-] а) сортировка слиянием
[-] б) пирамидальная сортировка
[+] в) сортировка вставками
На чём основан алгоритм Дейкстры:
[+] а) на жадном подходе
[-] б) на динамическом программировании
[-] в) на поиске с возвратом
Алгоритм, который не основан на жадном подходе:
[-] а) алгоритм Хаффмана
[+] б) алгоритм нахождения кратчайшего пути Беллмана-Форда
Что значит сказать «Асимптотически эффективнее»?
Ссылка на этот вопрос здесь.
Я думал, что алгоритм, более асимптотически эффективный, должен работать для всех входных данных, но я не понимаю причину «он работает для всех входных сигналов, кроме небольших».
Во-первых, оба алгоритма «работают» для всех входов. Вопрос в производительности.
В любом случае, как бы я сказал правильный ответ: « требует меньше шагов, чем на достаточно больших входах». Это все еще немного расплывчато, поскольку существует множество понятий «шаг», которые могут применяться, и алгоритм может быть асимптотически более эффективным по одной метрике и менее эффективным по другой. Эта формулировка избегает ценностного суждения о «лучшем выборе»; Есть много причин для выбора асимптотически менее эффективных алгоритмов или даже менее эффективных алгоритмов, когда заданы постоянные факторы / термины, такие как эффективность кэширования или простота реализации. Y X ‘ role=»presentation»> Икс Y ‘ role=»presentation»> Y
Что люди обычно имеют в виду, когда говорят что-то вроде этого:
В частности, ни одно из предложенных вами утверждений не следует, хотя люди часто предлагают второе.
К сожалению, более широкое сообщество людей, имеющих дело с алгоритмами, использует терминологию, которая ради простоты граничит с пустыми. (Делать точные и полезные утверждения об алгоритмах сложно!)
Алгоритм X называется асимптотически лучше, чем Y, если X занимает меньше времени, чем y, для всех входных размеров n, больших, чем значение n0, где n0> 0.
Я рекомендую вам изучать информатику из ресурсов CS, а не у программистов, которые когда-то читали о материалах в Википедии. (Да, это грубо, но я видел слишком много лжи, распространяемой в кругах программистов, даже на SO.)
Практические вопросы по анализу сложности времени
1. Что такое время, пространство, сложность следующего кода:
Объяснение: Первый цикл O (N), а второй цикл O (M). Поскольку мы не знаем, что больше, мы говорим, что это O (N + M). Это также можно записать как O (max (N, M)).
Поскольку дополнительное пространство не используется, сложность пространства постоянна / O (1)
2. Какова временная сложность следующего кода:
Объяснение:
Приведенный выше код выполняется всего раз
= N + (N — 1) + (N — 2) +… 1 + 0
= N * (N + 1) / 2
= 1/2 * N ^ 2 + 1/2 * N
O (N ^ 2) раза.
3. Какова временная сложность следующего кода:
Объяснение: Если вы заметили, j продолжает удваиваться, пока не станет меньше или равно n. Количество раз, мы можем удвоить число до тех пор, пока оно не станет меньше n, будет log (n).
Давайте возьмем примеры здесь.
для n = 16, j = 2, 4, 8, 16
для n = 32, j = 2, 4, 8, 16, 32
Таким образом, j будет работать за O (log n) шагов.
я бегу за н / 2 шагов.
Итак, общее количество шагов = O (n / 2 * log (n)) = O (n * logn)
4. Что это значит, когда мы говорим, что алгоритм X асимптотически более эффективен, чем Y?
Параметры:
Пояснение: В асимптотическом анализе мы рассматриваем рост алгоритма с точки зрения размера ввода. Говорят, что алгоритм X асимптотически лучше, чем Y, если X занимает меньше времени, чем y, для всех входных размеров n, больших, чем значение n0, где n0> 0.
Асимптотический анализ алгоритмов
Прежде чем приступать к обзору асимптотического анализа алгоритмов, хочу сказать пару слов о том, в каких случаях написанное здесь будет актуальным. Наверное многие программисты читая эти строки, думают про себя о том, что они всю жизнь прекрасно обходились без всего этого и конечно же в этих словах есть доля правды, но если встанет вопрос о доказательстве эффективности или наоборот неэффективности какого-либо кода, то без формального анализа уже не обойтись, а в серьезных проектах, такая потребность возникает регулярно.
В этой статье я попытаюсь простым и понятным языком объяснить, что же такое сложность алгоритмов и асимптотический анализ, а также возможности применения этого инструмента, для написания собственного эффективного кода. Конечно, в одном коротком посте не возможно охватить полностью такую обширную тему даже на поверхностном уровне, которого я стремился придерживаться, поэтому если то, что здесь написано вам понравится, я с удовольствием продолжу публикации на эту тему.
Во многих работах описывающих те или иные алгоритмы, часто можно встретить обозначения типа:
O(g(n)), Ω(g(n)), Θ(g(n)).
Давайте разбермся, что же это такое, но сначала я перечислю основные классы сложности применяемые при анализе:
f(n) = O(1) константа
f(n) = O(log(n)) логарифмический рост
f(n) = O(n) линейный рост
f(n) = O(n*log(n)) квазилинейный рост
f(n) = O(n^m) полиномиальный рост
f(n) = O(2^n) экспоненциальный рост
Если раньше вы не встречались с подобными обозначениями, не переживайте, после прочтения этой статьи, все станет намного понятнее.
А начнем мы с символа O.
Сначала приведу формальное определение:
(1.1) Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф-ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е. При c = c1 и n >= N, c*g(n) >=f(n).
Таким образом O – означает верхнее ограничение сложности алгоритма.
Давайте теперь попробуем применить это знание на практике.
Возьмем известную любому программисту задачу сортировки. Допустим нам необходимо отсортировать массив чисел, размерностью 10 000 000 элементов. Договоримся рассматривать худший случай, при котором для выполнения алгоритма понадобится наибольшее количество итераций. Не долго думая, мы решаем применять сортировку пузырьком как самую простую с точки зрения реализации.
Сортировка пузырьком позволяет отсортировать массив любой размерности без дополнительных выделений памяти. Вроде бы все прекрасно и мы с чистой совестью начинаем писать код (для примеров здесь и далее будет использоваться язык Python).
рис.1.
зеленая кривая соответствует графику ф-ии x^2 при c = 1, синия c = 5, красная c = 7
Здесь и далее на всех графиках ось абсцисс будет соответствовать размерности входных данных, а ось ординат кол-ву итераций необходимых для выполнения алгоритма.
Нас интересует только та часть координатной плоскости, которая соответствует значениям x большим 0, т.к. любой массив, по-определению, не может иметь отрицательный размер, поэтому, для удобства, уберем левые части графиков ф-ий, ограничившись лишь первой четвертью координатной плоскости.
рис.2.
зеленая кривая соответствует графику ф-ии x^2 при c = 1, синия c = 5, красная c = 7
Возьмем c2 = 7. Мы видим, что новая ф-ия растет быстрее предыдущей (красная кривая на рис.2). Из определения (1.1), делаем вывод, что при с2 = 7 и n >= 0, g(n) = 7*n^2 всегда больше или равна ф-ии f(n) = 5*n^2, следовательно наша программа имет сложность O(n^2).
Кто не до конца понял это объяснение, посмотрите на графики ф-ий и заметьте, что ф-ия отмеченная на нем красным, при n >= 0 всегда имеет большее значение по y, чем ф-ия отмеченная синим.
Что же можно сделать в этой ситуации, чтобы радикально ускорить сортировку? Необходимо, чтобы в худшем случае сложность алгоритма была меньше чем O(n^2). Поразмыслив немного, мы решаем, что не плохо бы было, придумать такой алгоритм, сложность которого не превышает O(n), т.е. является линейной. Очевидно, что в случае O(n) скорость работы программы возрастет в N раз, так как вместо N^2 итераций, нам необходимо будет сделать всего лишь N. Прогнозируемый прирост скорости отлично виден на рис.3.
Серой прямой обозначена линейная сложность, а три кривых показывают сложность n^2 при различных коэффициентах c.
Но оказывается, что сделать сортировку со сложностью O(n) в общем случае просто не возможно (док-во)! Так на какую же сложность мы в лучшем случае можем расчитывать? Она равна O(n*log(n)), что является теоретически доказаным минимальным верхнем пределом для любого алгоритма сортировки основанного на сравнении элементов. Это конечно немного не то, чего мы ожидали получить, но все же это уже и не O(n^2). Осталось найти алгоритм сортировки удовлетворяющий нашим требованиям.
Покопавшись в интернете, видим, что им удовлетворяет «пирамидальная сортировка». Я не буду вдаваться в подробности алгоритма, желающие могут прочитать о нем самостоятельно на wiki, скажу только, что его сложность принадлежит классу O(n*log(n)) (т.е. максимально возможная производительность для сортировки), но при этом, он довольно труден в реализации.
Посмотрим на графики ниже и сравним скорости возрастания кол-ва вычислений для двух рассмотренных алгоритмов сортировки.
рис.4.
Фиолетовая кривая показывает алгоритм со сложностью n*log(n). Видно, что на больших n, пирамидальная сортировка существенно выигрывает у сортировки пузырьком при любом из трех опробованных нами коэффициентах, однако все-равно уступает гипотетической сортировке линейной сложности (серая прямая на графике).
В любом случае, даже на медленном компьютере она будет работать гораздо быстрее, чем «пузырек» на быстром.
Остается открытым вопрос, целесообразно ли всегда предпочитать пирамидальную сортировку сортировке пузырьком?
рис.5.
Как видно на рис.5, при малых n, различия между двумя алгоритмами достаточно малы и выгода от использования пирамидальной сортировки — совсем незначительна, а учитывая, что «пузырек» реализуется буквально 5-6 строчками кода, то при малых n, он действительно является более предпочтительным с точки зрения умственных и временных затрат на реализацию 🙂
В заключении, чтобы более наглядно продемонстрировать разницу между классами сложности, приведу такой пример:
Допустим у нас етсь ЭВМ 45-ти летней давности. В голове сразу всплывают мысли о больших шкафах, занимающих довольно-таки обширную площадь. Допустим, что каждая команда на такой машине выполняется примерно за 10 миллисек. С такой скоростью вычислений, имея алгоритм сложности O(n^2), на решение поставленой задачи уйдет оооочень много времени и от затеи придется отказаться как от невыполнимой за допустимое время, если же взять алгоритм со сложностью O(n*log(n)), то ситуация в корне изменится и на расчет уйдет не больше месяца.
Посчитаем, сколько именно займет сортировка массива в обоих случаях
сверх-неоптимальный алгоритм (бывает и такое, но редко):
O(2^n) = оооооочень медленно, вселенная умрет, прежде чем мы закончим наш расчет…
пузырек:
O(n^2) = 277777778 часов (классический “пузырек”)
пирамидальная сортировка:
O(n*log(n)) = 647 часов (то чего мы реально можем добиться, применяя пирамидальную сортировку)
фантастически-эффективный алгоритм:
O(n) = 2.7 часов (наш гипотетический алгоритм, сортирующий за линейное время)
и наконец:
O(log(n)) = оооооочень быстро, жаль, что чудес не бывает…
Два последних случая (хоть они и не возможны в реальности при сортировке данных) я привел лишь для того, чтобы читатель ощутил огромную разницу между алгоритмами различных классов сложности.
На последок хочу заметить, что буквой O обычно обозначают минимальный из классов сложности, которому соответствует данный алгоритм. К примеру, я мог бы сказать, что сложность сортировки пузырьком равна O(2^n) и теоретически это было бы абсолютно верным утверждением, однако на практике такая оценка была бы лишена смысла.
Тест по информатике Алгоритмы и элементы программирования 11 класс
Тест по информатике Алгоритмы и элементы программирования 11 класс с ответами. Тест включает 24 задания с выбором ответа.
1. Какой из документов можно считать алгоритмом?
1) правила техники безопасности
2) инструкция по приготовлению пищи
3) расписание движения поездов
4) список книг в школьной библиотеке
2. Массовость — это свойство алгоритма, заключающееся в том, что:
1) алгоритм предназначен для множества исполнителей
2) алгоритм может использоваться на множестве однотипных задач
3) алгоритм состоит из множества конечных команд
4) в результате работы алгоритма может получаться множество различных результатов
3. Какую смысловую нагрузку несет блок?
1) блок начала-конца алгоритма
2) блок ввода-вывода
3) блок обработки
4) логический блок
4. Предлагается некоторая операция над двумя произвольными трехзначными десятичными числами:
1) записывается результат сложения старших разрядов этих чисел;
2) к нему дописывается результат сложения средних разрядов по такому правилу: если он меньше первой суммы, то полученное число приписывается к первому слева, иначе — справа;
3) итоговое число получают приписыванием справа к числу, полученному после второго шага, суммы значений младших разрядов исходных чисел.
Какое из перечисленных чисел могло быть построено по этому правилу?
1) 141310
2) 102113
3) 101421
4) 101413
5. У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2
2. умножь на 3
Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 0 числа 28, содержащей не более 6 команд, указывая лишь номера команд.
Например, программа 21211 — это программа:
умножь на 3
прибавь 2
умножь на 3
прибавь 2
прибавь 2
которая преобразует число 1 в 19.
6. Какое определение можно использовать для разветвляющегося алгоритма?
1) алгоритм, который может быть записан с помощью набора геометрических фигур
2) алгоритм, в котором команды выполняются последовательно друг за другом
3) алгоритм, в котором одни и те же действия исполняются многократно
4) алгоритм, в котором есть хотя бы одно условие
7. Какой тип алгоритма используется для вычисления площади треугольника по трем сторонам?
1) линейный
2) разветвляющийся
3) циклический
4) любой
8. Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:
Вперед n, где n – целое число, вызывающая передвижение черепашки на n шагов в направлении движения.
Направо m, где m – целое число, вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори 5 [Команда1 Команда2] означает, что последовательность команд в скобках повторится 5 раз.
Черепашке был дан для исполнения следующий алгоритм:
Повтори 5 [Повтори 4 [Вперед 40 Направо 90] Направо 120]
Какая фигура появится на экране?
9. Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив следующую программу
НАЧАЛО
ПОКА
ПОКА
вниз
КОНЕЦ ПОКА
ПОКА
вправо
КОНЕЦ ПОКА
КОНЕЦ ПОКА
КОНЕЦ
РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?
1) 22
2) 17
3) 19
4) 21
10. Определите значение целочисленных переменных x, y и t после выполнения фрагмента программы:
x := 5;
y := 7;
t := x;
x := y mod x;
y := t;
1) x=2, y=5, t=5
2) x=7, y=5, t=5
3) x=2, y=2, t=2
4) x=5, y=5, t=5
11. Определите значение переменной c после выполнения следующего фрагмента программы:
a := 6;
b := 15;
a := b – a*2;
if a > b
then c := a + b
else c := b – a;
12. Определите значение переменной y, которое будет получено в результате выполнения следующей программы:
var i, y: integer;
begin
y := 0;
for i := 1 to 4 do
begin
y := y * 10;
y :=y + i;
end
end.
13. Определите значение переменной y, которое будет получено в результате выполнения следующей программы:
var y : real; i : integer;
begin
y := 0;
i := 5;
while i>2 do
begin
i:=i − 1;
y := y + i * i
end;
end.
14. Определите значение переменной y, которое будет получено в результате выполнения следующей программы:
var y : real; i : integer;
begin
y := 0;
i := 1;
repeat
i :=2*i;
y := y + i
until i > 5;
end.
15. В программе описан одномерный целочисленный массив с индексами от 0 до 10. В приведенном ниже фрагменте программы массив сначала заполняется, а потом изменяется:
for i:=0 to 10 do
A[i]:= i + 1;
for i:=0 to 10 do
A[i]:= A[10-i];
Чему будут равны элементы этого массива?
1) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
2) 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
3) 11, 10, 9, 8, 7, 6, 7, 8, 9, 10, 11
4) 10, 9, 8, 7, 6, 5, 6, 7, 8, 9, 10
16. Все элементы двумерного массива A размером 5х5 равны 0. Сколько элементов массива после выполнения фрагмента программы будут равны 1?
for n:=1 tо 5 do
for m:=1 tо 5 do
A[n,m] := (m – n)*(m – n);
17. Дан фрагмент программы, обрабатывающей линейный массив A из 6 элементов.
for i:=1 tо 3 do
if A[i] > A[i+3] then
begin
c :=A[i];
A[i] :=A[i+3];
A[i+3] := c;
end;
Определите, какой из данных массивов станет упорядоченным по возрастанию после обработки алгоритмом.
1) 6, 3, 7, 35, 24, 13
2) 13, 6, 35, 3, 24, 7
3) 3, 7, 13, 24, 6, 35
4) 35, 3, 13, 24, 6, 7
18. Ниже представлен фрагмент программы, в которой описан одномерный целочисленный массив A и обрабатываются элементы массива с индексами от 1 до 10.
n := 10;
for i := 1 to n do begin
A[n+1-i] := 2*A[i];
end;
Перед началом выполнения фрагмента элементы массива имеют значения соответственно 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, т.е. A[1] = 1; A[2] = 2 и т.д.
Укажите значение, которое после выполнения указанного фрагмента программы имеют два или более рассмотренных в этом фрагменте элемента массива. Если таких чисел несколько, укажите наибольшее из них.
1) такого значения нет
2) 10
3) 8
4) 4
19. В программе описан одномерный целочисленный массив A с индексами от 0 до 10. Ниже представлен фрагмент этой программы, в котором значения элементов массива сначала задаются, а затем меняются.
for i:=0 to 10 do
A[i]:=i-1;
for i:=1 to 10 do
A[i-1]:=A[i];
A[10]:=10;
Как изменятся элементы этого массива после выполнения фрагмента программы?
1) все элементы, кроме последнего, окажутся равны между собой
2) все элементы окажутся равны своим индексам
3) все элементы, кроме последнего, будут сдвинуты на один элемент вправо
4) все элементы, кроме последнего, уменьшатся на единицу
20. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (2*n + 1), при n > 1
Чему равно значение функции F(4)?
1) 27
2) 9
3) 105
4) 315
21. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = F(n–1) – 2*G(n–1),
G(n) = F(n–1) + G(n–1), при n >=2
Чему равно значение величины G(5)/F(5)?
22. Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(‘*’);
if n > 0 then begin
F(n-3);
F(n div 2);
end
end;
Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(7)?
23. Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n 2 then
F := F(n-1)+F(n-2)+F(n-3)
else
F := n;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)?
Ответы на тест по информатике Алгоритмы и элементы программирования 11 класс
1-2
2-2
3-4
4-4
5. 121211
6-4
7-1
8-3
9-3
10-1
11-4
12. 1234
13. 29
14. 14
15-3
16-3
17-2
18-3
19-2
20-4
21-1
22-4
23. 42
24. 20