Введение в алгоритмы (глава 1-1)

Question

Просто прочитав эту книгу для удовольствия, это не домашнее задание.

Однако я уже запутался на первом главном назначение:

1-1 Сравнение запущенных раз

Для каждой функции F (N) и время т в следующей таблице, определить наибольший размер n проблемы, которая может быть решена за время t, предполагая, что алгоритм решения проблемы принимает f (n) микросекунды.

Что это значит?

Следующая таблица показывает несколько раз вдоль одной оси (1 секунда, 1 минута, один час и т. Д.), А другая ось показывает разные f (n), такие как lg n, sqrt (n), n, и т. д.

Я не уверен, как заполнить матрицу, потому что я не могу понять вопрос. Поэтому, если f (n) = lg n, он задает наибольшее значение n, которое может быть разрешено, например, 1 секунду, но проблема решает f (n) = lg n микросекунд? Что означает эта последняя часть? Я даже не знаю, как настроить уравнения/коэффициенты для решения этой проблемы, потому что я буквально не могу даже соединить смысл вопроса.

Мое зависание над предложением «при условии, что алгоритм для решения проблемы принимает f (n) микросекунд», потому что я не знаю, к чему это относится. Время для что алгоритм для решения что проблема принимает f (n) микросекунды? Так что, если я позвоню f (100), это займет lg 100 микросекунд? Поэтому мне нужно найти n, где f (n) = lg n microseconds = 1 секунда?

Это означает, что lg n микросекунд = 1 секунда, когда lg n микросекунд = 10^6 микросекунд, так что n = 2^(10^6)?

Answer 1

Для каждого времени T и каждой функции f(n), вы должны найти максимальное число n таким образом, что f(n) <= T

Например, f(n) = n^2, T=1Sec = 1000 ms:

n^2 <= 1000 
n <= sqrt(1000) 
n <= ~31.63 <- not an integer 
n <= 31 

любой функции f(n), и некоторое время T, вам также необходимо найти максимальное значение n и заполнить таблицу.