Обычно правило состоит в том, что если существует цикл из 1 в n элементов, то сложность O (n), а дальнейшие вложенные циклы n x O (n). Однако, когда мы говорим, что подпрограмма имеет сложность O (log n)?Есть ли способ определить, имеет ли подпрограмма журнал выполнения (n)?
Когда в каждой итерации мы уменьшаем размер проблемы быть фактором X, мы можем сказать, что проблема O(log n)
Например - Binary Search: в каждой итерации мы уменьшаем размер задачи по фактору от 2
Вы можете взять первый пример двоичного поиска. Объяснение сложности этого алгоритма можно взять из связанного вопроса how to calculate binary search complexity. Он показал, что вычисление такого типа сложности можно получить из повторения.
Проверка: http://stackoverflow.com/a/16785817/2128327 –
Не нужно понижать мой вопрос ... –