Итак, вероятно, вы изо всех сил пытаетесь понять, что такое логарифмическая или log(n) временная сложность.
Давайте углубимся в это, сначала вам нужно понять, что такое log?
скажем, я предполагаю, что число равно 8, теперь мне очень хочется узнать, какая степень 2 равна 8, или я могу сказать, в какой степени я поднял 2, чтобы получить 8. Да! вы правильно поняли, это 3, поэтому ответ 3 означает, что 2 в степени 3 равно 8, так что это Log (n). Теперь вы знаете, что такое log(n).
По сути, log(n) представляет собой показатель степени, до которого необходимо возвести 2, чтобы получить значение «n».
Вы также можете понять это, сказав: «Сколько раз мне следует разделить n по основанию (т. е. 2 в информатике), чтобы получить «1». Итак, вы должны разделить его на 3 раза, и именно это был ответ log(n).
Теперь давайте рассмотрим это на примере структур данных и алгоритмических временных сложностей.
Я хочу, чтобы ты подумал, когда
п=8 → журнал(8) = 3
п=16 → журнал(16) = 4
п=32 → журнал(32) = 5
вы замечаете, что значение log(n) увеличивается на единицу, и именно здесь вам нужно сосредоточиться на том, что при удвоении размера входных данных время увеличивается только на одну единицу, и в этом прелесть log(n). Рост log(n) остается впечатляюще скромным по мере роста значения N. Увеличение log(n), возникающее в результате удвоения N, составляет всего одну единицу. При использовании в сочетании с анализом сложности эта корреляция весьма примечательна. Привлекательность алгоритма с временной сложностью log(n) заключается в его эффективности. Выполнение метода предполагает увеличение только одной элементарной операции при увеличении или удвоении входных данных.
Я не буду усложнять, давайте разберемся на примере алгоритма двоичного поиска, сложность которого равна log(n). Итак, в этом алгоритме вы делите свой список пополам на каждой итерации, что означает, что вы сокращаете свою работу в 0,5 раза. на каждой итерации.
Предположим, у вас есть список [ 4, 5, 6, 7, 9, 21, 89, 129] с 8 элементами, поэтому n становится 8. целевой элемент = 1
Как только происходит первая итерация, вы сравниваете средний элемент, который равен 9 ≠ 1, но больше целевого значения, поэтому это означает, что все элементы после девяти будут больше целевого значения, поэтому нет возможности найти 1 в правой части, поэтому вы делите свой список пополам, как вы это делаете в log, игнорируя все элементы в правой части, начиная с 9. Помните, что мы рассматриваем отсортированный список в алгоритме двоичного поиска. Теперь интуитивно подумайте, что на первой итерации вы выполнили половину работы, поэтому время, необходимое для поиска целевого элемента, будет меньше. Итак, 50% работы сделано.
На второй итерации у вас есть этот список [ 4, 5, 6, 7 ] для поиска 1. Теперь вы сравниваете средний элемент 5 ≠ 1, но больше целевого, поэтому вы снова отбрасываете элементы с правой стороны, снова разделивколичество элементов на 2. Теперь 75 % работы выполнено.
На третьей итерации вы найдете средний элемент из обновленного списка, то есть [ 4 ]. вы сравниваете 4 ≠ 1, теперь снова вы разделите список на две части, но на этот раз элементы отсутствуют, поэтому в этом списке нет элемента 1. Теперь 100% работа завершена.
давайте свяжем это с log(n). Количество итераций или уровней, которые вы проходите, является значением log(n). Здесь было 3 итерации, а log(8) равен три, что означает, что после 3 итераций вы узнаете, присутствует ли целевой элемент в списке или нет. Следует помнить, что мы обнаруживаем, что сложность для наихудших случаев означает, что наихудшим случаем двоичного поиска является то, что элемент отсутствует в списке, а log(8) = 3 — это временная сложность наихудшего случая для списка двоичного поиска с 8 элементами. Возможно, вам повезет, если вы найдете свой элемент на первой итерации, но этот порядок роста, то есть большое О, расскажет вам о том, как ваш алгоритм будет работать в худшем случае. Поэтому всегда рассматривайте наихудшие сценарии для анализа эффективности ваших алгоритмов.
Подумайте по-другому: ваш список, содержащий 8 элементов и
1-й шаг: оставшиеся элементы 4 (8/2) или n/2
2-й шаг: оставшиеся элементы 2 (4/2) или n/4
3-й шаг: оставшиеся элементы 1 (2/2) или n/8
Если вы найдете это полезным, поделитесь и поставьте лайк. Спасибо 😄!
