Наихудшая временная сложность рекурсивной разделительной функции?

Question

Учитывая этот алгоритм:

void turtle_down(double val){
    if (val >= 1.0)
        turtle_down(val/2.0);
}

Из того, что я знаю, T (n) = T (n / 2) + O (1).

O (1) - это наихудшая временная сложность базовой функции, которая равна val! = 0.0 (я правильно понял?). И тогда рекурсивный вызов дает временную сложность T (n / 2), поскольку мы делим n перед рекурсивным вызовом. Это верно?

Но я не понимаю, как здесь сделать математику. Я не знаю, как мы доберемся до O (log n) (база 2). Кто-нибудь хочет объяснить или показать мне математику?

Answer 1

void turtle_down(double val){
    if (val != 0.0)
        turtle_down(val/2.0);
}

В приведенном выше коде условие теста if (val != 0.0) может не дать ожидаемого результата. Это будет go в бесконечное l oop. Рассмотрим случай, когда val = 32. Вы можете видеть, что оно никогда не достигнет 0 при повторном делении на 2.

Но если вы замените условие теста, скажем, if (val >= 1), то рекуррентное отношение для данной функции будет T (n) = T (n / 2) + O (1).

В этом случае временная сложность T (n) = O (log n).

Чтобы получить этот результат, вы можете использовать основную теорему.

Чтобы понять данную сложность, рассмотрите val = 32. Вы можете делить val многократно на 2, 5 раз, пока он не станет 1. Обратите внимание тот журнал 32 = 5. Из этого мы можем видеть, что количество вызовов, сделанных к функции, составляет log n.