общая временная сложность программы?

Question

предположим, что вы берете 'n' входных данных в массиве (и для этого вам нужно запустить al oop, который повторяет 'n' раз для 'n' различных местоположений), что будет иметь сложность O (n).

И затем вы пытаетесь выполнить операции, которые имеют O (log n) или меньше, чем O (n) сложность времени. Мой вопрос здесь заключается в том, что действительно ли важно иметь сложность этих операций меньше, чем O (n), поскольку вся ваша программа будет иметь как минимум O (n) временную сложность.

Answer 1

Действительно, сложность времени программы может зависеть от времени, которое требуется для чтения ввода. Например, если программа читает массив из входных данных, а затем выполняет один двоичный поиск в этом массиве, временная сложность составляет Θ (n) просто из-за чтения входных данных.

Также может преобладать временная сложность программы. к тому времени, которое требуется для генерации выхода. Например, дерево с n вершинами имеет n-1 ребер, поэтому многие алгоритмы на деревьях могут выполняться за Θ (n) времени; но если мы хотим напечатать матрицу смежности , то это невозможно сделать за время, превышающее Θ (n ² ), поскольку на выходе получается двумерный массив с n ² элементов.

Я думаю, что есть неявный дополнительный вопрос: Так как же алгоритм может работать менее чем за Θ (n) времени? Обратите внимание, что выше говорилось о программы, которые IO . Алгоритм двоичного поиска занимает Θ (log n) времени, поскольку чтение входных данных не выполняется самим алгоритмом двоичного поиска. Алгоритм является только частью программы; массив читается из ввода другой частью программы, поэтому он существует в памяти до запуска алгоритма, и алгоритм получает доступ к нему через ссылку . Это означает, что алгоритм получает входные данные размером n за время Θ (1).

Answer 2

Нет, это не имеет значения в терминах биг-О, так как в вашем примере ввод l oop O(n) доминирует над дальнейшими O(log n) операциями. См. Бесконечная асимптотика :

Большие обозначения O полезны при анализе эффективности алгоритмов. Например, время (или количество шагов), необходимое для решения проблемы размера n, может быть найдено равным T (n) = 4n2 - 2n + 2. По мере того, как n становится большим, член n2 станет доминирующим, так что всеми другими терминами можно пренебречь