1. Главная
  2. Библиотека
  3. Программирование
  4. Вычислительная сложность некоего алгоритма (например, в...
Решение задачи на тему

Вычислительная сложность некоего алгоритма (например, вычисления оптимального дорожного маршрута),   n O n n 2 2   , где n – объём входной информации. У первого алгоритма объём входной информации n1=6, и он был реализован за t1=0,432 с. За какое время

  • Программирование
  • #Основы алгоритмизации и программирования
  • #Структуры и алгоритмы обработки данных
Вычислительная сложность некоего алгоритма (например, вычисления оптимального дорожного маршрута),   n O n n 2 2   , где n – объём входной информации. У первого алгоритма объём входной информации n1=6, и он был реализован за t1=0,432 с. За какое время

Условие:

Вычислительная сложность некоего алгоритма (например,
вычисления оптимального дорожного маршрута),
 
n O n n 2
2
 
, где n – объём
входной информации. У первого алгоритма объём входной информации n1=6,
и он был реализован за t1=0,432 с. За какое время t2 будет реализован
алгоритм на том же процессоре, если объём входной информации n2=10?

Решение:

Для решения задачи нам нужно использовать информацию о вычислительной сложности алгоритма и соотношение времени выполнения для разных объемов входной информации.

  1. Определим вычислительную сложность: Дана сложность алгоритма: O(n2)O(n^2). Это означает, что время выполнения алгоритма пропорционально квадрату объема входной информации.

  2. Запишем соотношение времени выполнения: Если t1t1 — время выполнения для объема входной информации n1n1, и t2t2 — время выполнения для объема входной информации n2n2, то можно...

Выбери предмет