#time-complexity
#временная сложность
Вопрос:
Я просто хотел убедиться, что я иду в правильном направлении. Я хочу найти максимальное значение массива путем рекурсивного его разделения и найти максимальное значение каждого отдельного массива. Поскольку я разделяю его, это было бы 2 * T (n / 2). И поскольку в конце мне нужно провести сравнение для 2 массивов, у меня есть T (1). Итак, будет ли мое рекуррентное отношение таким:
T = { 2 * T (n / 2) 1, когда n> = 2;T (1), когда n = 1;
и, следовательно, моя сложность была бы Тета (nlgn)?
Ответ №1:
Составленная вами формула кажется примерно правильной, но ваш анализ не идеален.
T = 2*T(n/2) 1 = 2*(2*T(n/4) 1) 1 = ...
Для i-й итерации вы получите:
Ti(n) = 2^i*T(n/2^i) i
теперь то, что вы хотите знать, для чего i делает n / 2 ^ i равным 1 (или практически любой константе, если хотите), чтобы вы достигли конечного условия n = 1.
Это было бы решением для n / 2 ^ I = 1 -> I = Log2 (n). Поместите это в уравнение для Ti, и вы получите:
TI(n) = 2^log2(n)*T(n/2^log2(n)) log2(n) = n*1 log2(n) = n log2(n)
и вы получаете T (n) = O (n log2 (n) (точно так же, как сказал @bdares) = O (n) (точно так же, как сказал @bdares)
Комментарии:
1. Нормально ли писать O (n log (n))? Похоже, что O (n) было бы достаточно в каждом событии. На самом деле, зачем так усложнять это? Я чувствую, что писать O (n log (n)), хотя и не неправильно, глупо. Мы не пишем O (n ^ 2 n) для Bubblesort. Я что-то упускаю? Если вы просто используете это в иллюстративных целях, хорошо; Я думаю, для меня немного странно не видеть, как выполняется последний шаг… так что, если это так, просто примите это как критику стиля, а не содержания.
2. @bdares Ты прав. Я должен был добавить последний шаг. Я избегаю пропускать часть (n log (n)), когда объясняю это, чтобы избежать путаницы, но я должен обязательно добавить и последнюю часть.
Ответ №2:
Нет, нет… вы тратите O (1) времени на каждую рекурсию.
Сколько их?
Существует N листьев, так что вы знаете, что это как минимум O (N).
Сколько вам нужно сравнить, чтобы найти абсолютный максимум? Это O (log (N)).
Сложите их вместе, не умножайте. O (N log (N)) — это ваша временная сложность.
Комментарии:
1. о, я понимаю. я был немного смущен, потому что это выглядело похоже на сортировку слиянием. итак, рекуррентное отношение также правильное или неправильное?
2. Эх .. я действительно не совсем понимаю это, но это выглядит правильно. Каждый уровень добавит 1, затем 2, затем 4, затем 8 и так далее… итак, я был неправ. Это займет 1 2 4 8 … 2^ регистрируйте (n) время для каждого шага и, следовательно, потребуется O (2 * n) времени, что равно O (n) времени. Кстати, то же самое, что O (N log (N)), что также равно O (n), но первое объяснение было неверным.