ну тогда мы посмотрим на этот вопрос, мы можем его проанализировать.
давайте начнем с примеров, поскольку, исследуя их, мы сможем лучше понять, как их решать (другая проблема заключается в том, как представлять данные, которые у нас есть, но это компьютерный опыт, позволяющий узнать, как представлять данные для чтения). ).
(подсказка, все, что ниже 1, округляется до 1
T (1) = 1
Т (2) = 1 + 1
Т (3) = Т (1,5) + 1
T (4) = T (2) + 1
Т (5) = Т (2,5) + Т (1,25)
Т (2,5) = Т (1,25) + 1
Т (6) = Т (3) + Т (1,3333)
Теперь, если мы делаем раунды, мы можем понять, что между 1 и 2 может принимать верхнюю границу 2 или нижнюю границу 1.
в качестве подсказки я скажу, что если вы докажете, что когда вы берете все верхние границы и получаете желаемую тета, и если вы берете все желаемую нижнюю границу, то вы доказываете, что она ограничена тем же тета. *
теперь давайте рассмотрим верхнюю тета
T (1) = 1
T (2) = 1 + 1
T (3) = T (2) + 1 = (1 + 1) + 1
T (4) = T (2) + 1 = (1 + 1) + 1
T (5) = T (3) + T (2) = (1 + 1 + 1) + (1 + 1)
T (6) = T (3) + T (2) = (1 + 1 + 1) + (1 + 1)
Вы видите его линейным?
Вы можете выйти из фурмулы из этого?
вот как вы подходите к таким вопросам.
удачи,
не забывайте анализ нижней границы.