1) REORDER следующую эффективность от наименьшего к наибольшему:
2^n, n!, n^5, 10000, nlog2(n)Некоторые вопросы сложности
Мой Ans-> 10000 < nlog2 (п) < п^5 < 2^п < п!
Исправить?
2) Эффективность алго. n^3, если шаг в этом algo. занимает 1 наносекунду. (10^-9 сек.). Сколько времени занимает алго. обрабатывать ввод размером 1000?
Я не знаю ... Это (1000)^3 * 10^-9?
Вопрос один в порядке. Во-вторых, я бы предположил, что ваш ответ - это то, что они ищут, но если по n^3 вы имеете в виду O (n^3), вы не можете на самом деле ответить (если это не используется «алгоритмическая эффективность» I незнакомец).
Сложность Big-O дает асимптотическую оценку поведения алгоритма. Мы знаем, что для «большого» n, что O (n^3) больше времени, затраченного на выполнение алгоритма на входе размера n. Обратите внимание на два оговорки - «большое n» и «асимптотическое ограничение». Нет ничего, чтобы остановить ввод размера 1000 в два раза длиннее ввода размера 2000, если существует некоторое m такое, что для всех n> m n^3 ограничивает время выполнения. Кроме того, нет ничего, чтобы остановить алгоритм, принимающий 1 наносекунду на каждом входе, поскольку n^3 все еще является привязкой к времени выполнения - это просто очень пессимистично.
Вот почему большая нотация O часто используется ограниченным образом в практических ситуациях. Он дает справедливый обзор «наихудшего случая», но не говорит о каком-либо сценарии использования. Для более практичного (но часто упускаемого) класса сложности сложности google для «Большой тета».
В определении big-O также важен масштабный коэффициент; было бы более технически правильно говорить «до тех пор, пока существуют константы * m * и * k * такие, что для всех * n *> * m *, * k n * ³ ограничивает время выполнения». Big-theta отлично, но я не думаю, что практическое использование big-O ограничено тем фактом, что оно обычно используется для ссылки на ограниченную связь, даже если оно строго не требует этого. Это проще, и иногда математика на истинной тете связана слишком волосатой, чтобы ее стоить. – jtb
Хорошая точка, № 2 технически неопровержимо из приведенной информации, хотя я бы догадался, что авторы вопроса хотели получить только тот ответ, который он предоставил. : -/ – Kip
Да, есть коэффициент масштабирования - я оставил его преднамеренно, чтобы избежать еще большей путаницы для вопрошающего, но, спасибо, что упомянул об этом :) –
Оба ответа верны
1) Да, это правильно.
2) Это также верно. Размерный анализ: (1000^3 шага) * 10^(- 9) секунд/шаг
Если это домашнее задание, это ужасные вопросы. –
оба ваши ответы верны. –