DeiP
@DeiP
Student

Как решить задачу на сложность алгоритмов ниже?

Привет, помогите решить:
Компьютер А в 100 раз быстрее компьютера B. Если компьютер В за 1 час обрабатывает n-ое количество входных данных алгоритмом с линейной сложностью, то сколько данных за это же время обработает компьютер А, если сложность алгоритма обработки:
а) Линейная (n)
б) Квадратичная (n^2)
в) Кубическая (n^3)
г) Экспоненциальная (2^n)

Правильно ли я понимаю:
а) 100n
б) 10n
в) Корень кубический из 100n (4.64159n)
г) log(2)100 n (6,644n)
  • Вопрос задан
  • 522 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
г) не правильно подсчитано.

Составьте уравнение. Вот есть у вас функция времени для n входных данных f(n) на компе B. На компе A время выполнения будет - f(n)/100, ведь он в 100 раз быстрее.

Теперь обозначьте за x объем данных на компе A, который надо найти. Тогда у вас f(x)/100 = f(n). Подставьте нужную функцию вместо f() и найдите x. Спойлер, будет похоже, но не то, что у вас в вопросе указано.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы