Задача на сложность алгоритмов

@DPdw · Регистрация: 10.01.2020

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

@AndryS1 · 10.01.2020, 23:12

Вроде так, если не прокатит можно пример ввода и ожидаемого вывода?

C++

#include <cmath>
#include <iostream>
 
uint64_t A1(uint64_t B)
{
    return uint64_t(B * 100);
}
uint64_t A2(uint64_t B)
{
    return uint64_t(std::sqrt(B) * 100);
}
uint64_t A3(uint64_t B)
{
    return uint64_t(std::pow(B, 1.0 / 3.0) * 100);
}
uint64_t A4(uint64_t B)
{
    return uint64_t(std::pow(2, 1.0 / B) * 100);
}

@Kuzia domovenok · 11.01.2020, 01:39

Сообщение от DPdw

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

вообще не факт, что время работы алгоритма равно сложности.
Не зря, говоря о сложности алгоритмов употребляют всякие "о-большое, о-малое", потому что явного равенства между временем работы и всякими N-квадрат, N-куб и.т.д. ставить нельзя

@AndryS1 · 11.01.2020, 02:46

Сообщение от Kuzia domovenok

Не зря, говоря о сложности алгоритмов употребляют всякие "о-большое, о-малое", потому что явного равенства между временем работы и всякими N-квадрат, N-куб и.т.д. ставить нельзя

А тогда как это решить?

@DPdw 0 / 0 / 0 Регистрация: 10.01.2020 Сообщений: 1
		1
	Задача на сложность алгоритмов 10.01.2020, 22:55. Показов 748. Ответов 3 Метки программирование, сложность алгоритма (Все метки) Компьютер А в 100 раз быстрее компьютера B. Если компьютер В за 1 час обрабатывает n-ое количество входных данных алгоритмом с линейной сложностью, то сколько данных за это же время обработает компьютер А, если сложность алгоритма обработки: а) Линейная (n) б) Квадратичная (n^2) в) Кубическая (n^3) г) Экспоненциальная (2^n) __________________ Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь 0

@Kuzia domovenok 3982 / 3252 / 909 Регистрация: 25.03.2012 Сообщений: 12,089 Записей в блоге: 1
	11.01.2020, 01:39	3
	Сообщение от DPdw Компьютер А в 100 раз быстрее компьютера B. Если компьютер В за 1 час обрабатывает n-ое количество входных данных алгоритмом с линейной сложностью, то сколько данных за это же время обработает компьютер А, если сложность алгоритма обработки: а) Линейная (n) б) Квадратичная (n^2) в) Кубическая (n^3) г) Экспоненциальная (2^n) вообще не факт, что время работы алгоритма равно сложности. Не зря, говоря о сложности алгоритмов употребляют всякие "о-большое, о-малое", потому что явного равенства между временем работы и всякими N-квадрат, N-куб и.т.д. ставить нельзя 0

@AndryS1 653 / 466 / 183 Регистрация: 23.04.2019 Сообщений: 1,987
	11.01.2020, 02:46	4
	Сообщение от Kuzia domovenok Не зря, говоря о сложности алгоритмов употребляют всякие "о-большое, о-малое", потому что явного равенства между временем работы и всякими N-квадрат, N-куб и.т.д. ставить нельзя А тогда как это решить? 0

Опции темы