Divide and Conquer alg, который работает в постоянное время?

Question

Можете ли вы указать мне пример алгоритма разделения и покорения, который работает в ПОСТОЯННОЕ время! Я в ситуации «OMG! Я не могу думать о такой вещи». Назовите меня чем-нибудь, пожалуйста. Спасибо

Я знаю, что alg, который следует за следующей изоляцией: T(n) = 2T(n/2) + n будет merge sort. Мы делим проблему на две подзадачи - каждый из размеров n/2. Затем мы занимаем n время, чтобы покорить все в один отсортированный массив.

Я также знаю, что T(n) = T(n/2) + 1 будет binary search.

Но что T(n) = 1?

Answer 1

Для алгоритма разделяй и властвуй бежать в постоянной времени, он должен сделать не больше, чем фиксированное количество работы на любом входе. Поэтому он может сделать не более фиксированное количество рекурсивных вызовов на любом входе, так как если количество вызовов было неограниченным, общая выполненная работа не была бы постоянной. Кроме того, он должен выполнять постоянный объем работы во всех этих рекурсивных вызовах.

Это устраняет в основном любое разумное отношение повторения. Все формы

Т (п) = аТ (п/б) + О (п ^к)

сразу может быть и речи, так как количество рекурсивных вызовов будет расти как функция входа n.

Вы можете сделать некоторые очень надуманные алгоритмы разделения и покоя, которые работают в постоянное время. Например, рассмотрим эту проблему:

Возврат первого элемента входного массива.

Это может технически быть решена с разделяй и властвуй, отметив, что

• Первый элемент массива на один элемент равен самому себе.
• Первый элемент массива n-элементов - это первый элемент подмассива только первого элемента.

Рецидив затем

Т (п) = Т (1) + O (1)

Т (1) = 1

Как видно , это очень странно выглядящий рецидив, но он работает.

Я никогда не слышал об этом, как это происходит на практике, но если я думаю о чем-либо, я попытаюсь обновить этот ответ с подробностями. (Примечание: я не ожидаю когда-либо обновить этот ответ.^_ ^)

Надеюсь, это поможет!