До того, как я начал заниматься веб-разработкой, я был учителем математики. Поэтому вопросы о сложности времени и их идея должны быть для меня на 100% легкими, верно? Может быть нет.
Мне нравятся хорошие примеры при обучении, поэтому я решил собрать их здесь, используя console.log (). Также небольшое примечание, но часть моей борьбы заключалась в том, что люди показывали мне график временной сложности, где время не было на оси абсцисс.
Я собираюсь использовать отсортированный массив чисел от 1 до 20. Сначала я собираюсь определить, является ли массив уникальным. Я включил строку console.log во весь свой код.
В приведенном ниже случае имеется 20 элементов, и перед возвратом значения true функция ниже выведет 20 индексов. Вход 20 и выход 20 определенно являются линейной функцией в математике. Временная сложность здесь линейна, O (n).
Теперь, возможно, ваш первый инстинкт - написать два четырех цикла, которые проходят через массив. Это будет случай n², как в случае с массивом, с которого я начал, console.log () 400 раз.
Теперь давайте выполним поиск, который использует O (n), а не двоичный поиск, использующий O (log n).
При использовании двоичного поиска не нужно выполнять столько же времени, так как он будет смотреть на среднюю точку, а затем проверять половину оставшихся данных, прежде чем найти среднюю точку следующей половины данных.
Чтобы найти последний элемент, 20, вот console.log двоичного поиска.
Поскольку я смотрю на меньшие наборы данных, может показаться, что 5 console.logs против 20 - не такая уж большая проблема, но мы должны принять во внимание тот факт, что наборы данных будут иметь гораздо больше, чем 20 элементов, и что здесь важна сложность времени.
