Т (п) = п + Т (п/2)вычисления рекуррентное соотношение Т (п) = п + Т (п/2)
= п + N/2 + Т (п/4)
= п + п/2 + п/4 + Т (п/8)
= п + п/2 + п/4 + ... + п/(2^(к- 1)) + Т (п/2^к)
- >>>
, и я не знаю, как г о, чтобы получить большую формулу Oh. , пожалуйста, помогите мне
Я предполагаю, что есть какие-то начальные условия, такие как T(1) = 0, о которых вы нам не говорите.
Если да, то ответ O(log n).
Подумайте, как вы могли бы выработать T(2), T(4), T(8), T(16) и т. Д. Каждому требуется только один дополнительный шаг.
T(1) = T(2^0) calls the method recursively 0 times.
T(2) = T(2^1) calls the method recursively 1 time
T(4) = T(2^2) calls the method recursively 2 times
T(8) = T(2^3) calls the method recursively 3 times
Другими словами, количество шагов - это мощность. Это означает, что вам нужно взять логарифмы, чтобы получить ответ.
hmm Я не уверен, что T (1) = 0, но когда я думаю о «вызовах», это имеет смысл, я использую математический расчет для его решения, но я получаю O (n) Теперь я уверен, почему это O (log n). Я выложу свой расчет – IAMBEAST
, но T (n) не только о том, сколько раз звонит рекурсивным вызовам. Я думаю, – IAMBEAST
@ IAMBEAST. Вы правы, это не так, но в этом случае это одно и то же, потому что единственное другое операция является добавлением, которое является «O (1)». Ваш расчет неисправен двумя способами. Во-первых, вы, похоже, смущены тем, что вы работаете над «T (n)» или временной сложностью. Во-вторых, вы не можете использовать сумму в бесконечности геометрической последовательности - предположительно «n» является целым числом, а не действительным числом, которое может быть уменьшено вдвое произвольно много раз. –
Я голосую, чтобы закрыть этот вопрос как не по теме, потому что это не вопрос программирования. Попробуйте http://math.stackexchange.com – Matt