Первый шаг в изучении структур данных и алгоритмов
временная сложность
Каковы наиболее распространенные временные сложности
- "O(1)": Постоянная сложность
- "O(log n)": Logarithmic ComPlexity логарифмическая сложность
- "O(n)": Linear ComPlexity линейная временная сложность
- "O(n^2)": N квадрат ComPlexity квадрат
- "O(n^3)": N кубическая сложность
- "O(2^n)": Индекс экспоненциального роста
- "O(n!)": Факторный факториал
При анализе временной сложности предыдущие коэффициенты не учитываются, например, если O(1), это не означает, что его сложность равна 1, она может быть и 2, 3, 4..., лишь бы она была постоянное время, оба выражаются в O (1)
Как посмотреть на временную сложность фрагмента кода?
Самый распространенный способ — посмотреть на этот код напрямую, сколько раз он будет запускаться в зависимости от n
O(1)
$n=100000;
echo 'hello';
O(?)
$n=100000;
echo 'hello1';
echo 'hello2';
echo 'hello3';
Первый фрагмент кода, каким бы ни было n, выполняется только один раз, поэтому его временная сложность равна O(1). Второе на самом деле то же самое, нам все равно, какой коэффициент. Хотя второй фрагмент кода будет выполнять эхо-вывод 3 раза, независимо от значения n, он будет выполняться только 3 раза, поэтому его временная сложность также равна"постоянная сложность", что равно O(1)
Посмотрите на следующие два фрагмента кода:
O(n)
for($i = 1; $i <= $n; $i++) {
echo 'hello';
}
O(n^2)
for($i = 1; $i <= $n; $i++) {
for($j = 1; $j <= $n; $j++) {
echo 'hello';
}
}
Эти два фрагмента кода различаются числом n, и количество раз, когда он выполняется, также меняется.Количество раз, когда первый фрагмент кода выполняется, линейно связано с n, поэтому его временная сложность равна"O(n)".
Второй фрагмент кода представляет собой вложенный цикл.Когда n равно 100, оператор вывода внутри будет выполняться 10 000 раз, поэтому его временная сложность равна"O(n^2)". Если цикл во втором фрагменте кода не вложенный, а параллельный, то его временная сложность должна быть O(2n), поскольку нам не важен постоянный коэффициент впереди, поэтому его временная сложность равна"O(n)"
O(log n)
for($i = 1; $i <= $n; $i = $i*2) {
echo 'hello';
}
O(k^2)
fib($n) {
if ($n < 2) {
return $n;
}
return fib($n-1) + fib($n-2);
}
В первом кусочке кода, когда n = 4, цикл выполняется дважды, поэтому связь между количеством исполнений внутри цикла и N является log2 (n), поэтому сложность времени является логарифмической сложностью"O(logn)". Второй абзац представляет собой последовательность Фибоначчи (Fibonacci).Вот форма рекурсии, которая включает в себя, как вычислить временную сложность рекурсивной программы при ее выполнении.Его ответ"k^n", k является постоянной и экспоненциальной, поэтому простое рекурсивное нахождение последовательности Фибоначчи очень медленно и имеет экспоненциальную временную сложность. Как получается конкретная экспоненциальная временная сложность, будет подробно объяснено позже. Давайте посмотрим на кривые различной временной сложности
Из этого рисунка видно, что когда n относительно невелико, менее 10 слов, факт почти разной временной сложности. Но если и когда n продолжают расти, экспоненциальный рост будет очень быстрым. Поэтому, когда мы пишем программу, если мы можем оптимизировать временную сложность, например, упали с 2 ^ n n ^ 2, то, исходя из этой кривой, когда n большое, когда прибыль получается очень высокой. Таким образом, это говорит нам о том, что при нормальной разработке бизнес-кодов обязательно следует понимать их собственную временную и пространственную сложность, а также привычку после того, как код написан, подсознательно анализировать время и пространство этой сложности процедуры.
Как видно из рисунка, если ваша временная сложность разбита, то на самом деле потери машин или ресурсов, принесенных в компанию, будут увеличиваться на сотни или тысячи при увеличении n, а если вы можете упростить, то это большие затраты. экономия для компании
Для разных программ достижение одной и той же цели в письменной форме может привести к разной временной сложности. См. простой пример ниже
从1加到2一直加到n，求它的和
Когда я изучал математику в начальной школе, все знали, что есть два метода.Первый метод заключается в использовании программы для решения задачи методом перебора, который состоит в накоплении от 1 до n. Это слой циклов, и столько раз, сколько n, выполняется накопление, поэтому его временная сложность равна"O(n)"
$sum = 0;
for ($i=1; $i <=$n; $i++) {
$sum += $i;
}
Метод 2 заключается в использовании математической сводной формулы:
y = n*(n+1)/2
С этой формулой программа Discovery имеет только строку, поэтому его временная сложность является O (1). Таким образом, вы можете видеть, что разные методы программы, окончательный результат такой же, но его временной сложность очень отличается.
Для рекурсии, как проанализировать временную сложность?
Для рекурсии ключом является понимание ее рекурсивного процесса и того, сколько раз рекурсивный оператор выполняется в целом. Если это цикл, то легко понять, что цикл из n раз выполняется n раз. Затем рекурсия, по сути, она вложена послойно, по сути, много раз, мы просто рисуем древовидную структуру порядка выполнения рекурсии, которая называется деревом рекурсии ее рекурсивного состояния. В качестве примера возьмем n-й член предыдущей последовательности Фибоначчи (Fibonacci).
Fib：0,1,1,2,3,5,8,13,21...
F(n) = F(n-1)+F(n-2)
Я столкнулся с таким вопросом в предыдущем интервью, и оно было написано в простейшем способе реализации рекурсии.
fib($n) {
if($n < 2) {
retuen $n;
}
return fib($n-1)+fib($n-2);
}
Как упоминалось ранее, его временная сложность равна"O(k^n)"Итак, как вы его получите, вы можете проанализировать его, предположим, что n занимает 6, чтобы вычислить FIB (6), как выполнить этот код
Следовательно, если вы хотите вычислить F(6), две ветви, F(5) и F(4), являются как минимум еще двумя операциями.
Если вы хотите рассчитать F(5), вы можете получить его таким же образом, вам нужно урегулировать F(4) и F(3). Если вы хотите рассчитать F(4), вы можете получить его таким же образом, вам нужно сопоставить F(3) и F(2). Здесь можно увидеть два явления:
- Для каждого дополнительного слоя количество работающих узлов в два раза больше, чем у верхнего уровня: первый слой имеет только 1 узел, второй слой имеет 2 узла, третий слой имеет 4 узла, а следующий слой имеет 8 узлов. Поэтому для каждого слоя количество узлов, то есть количество исполнений, увеличивается в геометрической прогрессии. Видно, что когда n, он выполняется 2^n раз
- Второй можно наблюдать,"Есть повторяющиеся узлы"Появляется в дереве выполнения, например F(4) и F(3) на рисунке. Если вы продолжите расширять это дерево, вы обнаружите, что F(4), F(3) и F(2) будут вычисляться много раз.
Именно потому, что существует так много избыточных вычислений, временная сложность нахождения числа Фибоначчи из 6 чисел становится степенью 2^6. Поэтому, если вы встретите такого рода вопрос на собеседовании, постарайтесь не писать его в таком ключе, иначе будет прям холодно. Можно добавить кеш, чтобы эти промежуточные результаты можно было кешировать (хранить в массиве или хэше, там многократно вычисляемые значения, а потом находить их изнутри), или напрямую использовать цикл для записи
Основная теорема
Ввести вещь, называемую основной теоремой.Почему эта теорема важна?Это из-за основной теоремы.На самом деле, она используется для решения всех рекурсивных функций.Как вычислить ее временную сложность. Саму основную теорему относительно сложно доказать математически (основную теорему можно найти в Википедии: https://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90% 86 )
Другими словами, любая функция «разделяй и властвуй» или рекурсивная функция может вычислить свою временную сложность, а как вычислить ее — с помощью основной теоремы. Если посложнее, то как упростить в практические приемы, на самом деле ключ вот эти четыре, вообще запомните.
Как правило, в различных рекурсивных ситуациях есть четыре вышеперечисленных ситуации, которые используются на собеседованиях и в обычной работе.
"Бинарный поиск": обычно происходит, когда упорядочена сама последовательность, чтобы найти целевое число в упорядоченной последовательности, поэтому она каждый раз делится на две части и проверяется только одна сторона В этом случае окончательная временная сложность равна"O(logn)"
"Обход бинарного дерева": Если это обход бинарного дерева, его временная сложность равна"O(n)". Потому что из основной теоремы можно знать, что его нужно каждый раз делить на две части, но после каждого разбиения на две части он имеет одинаковую временную сложность с каждой стороны. Наконец, его рекуррентная формула на рисунке принимает вид T(n)=2T(n/2)+O(1). Наконец, в соответствии с этой основной теоремой можно сделать вывод, что время его работы равно O(n). Конечно, есть и упрощенный способ мышления, то есть, если бинарное дерево будет пройдено, оно будет"Каждый узел посещается один и только один раз, поэтому его временная сложность равна O(n)."
"2D-матрица (поиск оптимальной отсортированной матрицы)": Двоичный поиск выполняется в отсортированной двумерной матрице.В это время временная сложность также может быть получена с помощью основной теоремы."O(n)", просто помни
"Сортировка слиянием": Оптимальный способ сортировки"nlogn", временная сложность сортировки слиянием составляет O(nlogn)
Общие вопросы интервью о временной сложности
"Обход бинарного дерева - предварительный порядок, обратный порядок, обратный порядок: какова временная сложность?"
ответ:"O(n)", где n представляет общее количество узлов в дереве в двоичном дереве.Независимо от того, каким образом он проходится, каждый узел посещается и посещается только один раз, поэтому его сложность линейна по отношению к общему количеству узлов в двоичном дереве, что равно O(n)
"Обход графов: какова временная сложность?"
Отвечать:"O(n)", каждый узел в графе посещается только один раз, поэтому временная сложность также равна O(n), где n — общее количество узлов в графе.
"Алгоритм поиска: какова временная сложность DFS (сначала в глубину) и BFS (сначала в ширину)?"
Отвечать:"O(n)", в следующих статьях эти два алгоритма будут подробно представлены (n — общее количество узлов в пространстве поиска).
"Бинарный поиск: какова временная сложность?"
Отвечать:"O(logn)"
космическая сложность
Ситуация пространственной сложности и временной сложности на самом деле похожа, но проще. Его можно проанализировать самым простым способом. Есть два основных принципа:
Если вы открываете массивы в своем коде, то длина массива в основном зависит от вашей пространственной сложности. Например, если вы открываете одномерный массив, то ваша пространственная сложность равна O (n).Если вы открываете двумерный массив, длина массива равна n ^ 2, тогда пространственная сложность в основном равна n ^ 2.
Если есть рекурсия, то наибольшая глубина ее рекурсии является максимальным значением вашей пространственной сложности. Если вы рекурсивно открываете массив в своей программе, то пространственная сложность будет максимальной из двух.
Находить то же самое в быстро меняющихся технологиях — основная конкурентоспособность технического специалиста. Единство знания и действия, сочетание теории с практикой