Полное руководство по нотации «Большое О» (временная и пространственная сложность алгоритмов)

Попробуйте нашу полную платформу: https://nas.io/backtobackswe 📹 Интуитивно понятные видеообъяснения ❓ Новые, ранее не встречавшиеся вопросы 🔎 Получите все решения Нотация Big O очень важна для собеседований в области разработки программного обеспечения. Она действительно демонстрирует вашу способность к критическому мышлению, как у инженера. Вопрос, на который отвечает Big O, звучит так: «Как скорость этого алгоритма масштабируется по мере масштабирования входных данных системы?» Вот и все. Это вопрос масштаба, а не точных чисел. Именно поэтому мы опускаем константы. Точнее, это означает, что если мы дадим этому алгоритму ОЧЕНЬ БОЛЬШИЕ входные данные, какова будет ВЕРХНЯЯ ГРАНИЦА времени выполнения? Чем будет определяться это поведение в хвосте распределения? Мы говорим O(N), но что такое n? Никогда не говорите «n», не зная, что такое n. Знайте, что такое n. Это длина строки? Это длина массива? Это количество узлов в дереве? Что это? Когда мы говорим о «большом О», мы обычно вычисляем наихудший случай и указываем его как временную сложность, тем самым устанавливая верхнюю границу, которую он не может преодолеть и которая находится очень близко к ней. Пространство вычисляется так же, как и временная сложность, не путайте, но вопрос смещается к: «как масштабируется использование пространства этим алгоритмом по мере масштабирования входных данных системы?» Я знаю, вы хотите запомнить «форму» и «шаблон» определенного кода, но не делайте этого. Понимайте, что происходит. На самом деле вам нужно знать, что происходит, чтобы понимать их в наихудшем, среднем и наилучшем случаях (хотя нас больше всего интересуют средний и наихудший). Это поможет вам найти оптимальное решение, если вы знаете наилучшую достижимую сложность, это подразумевает метод, который, как известно, имеет именно такую ​​временную сложность. Если вы слышите log(n), значит, решение будет основано на бинарном поиске или каком-то алгоритме, который каким-то образом уменьшает входные данные вдвое… На собеседовании нельзя гадать, и в этом вся суть: вас поставят в неловкое положение, и вам придётся объяснять. Объясняйте уверенно, будьте точны. Если вы не понимаете, почему что-то имеет такую ​​сложность, не миритесь с этим, поймите, выясните, почему, и действительно подумайте о том, что происходит. Это сделает вас более сильным мыслителем и позволит решать всё более сложные задачи. Кроме того, сложность рекурсивных и алгоритмов с возвратом сложнее вычислить, поэтому просто практикуйтесь, это придёт со временем и опытом. Не отчаивайтесь... ++++++++++++++++++++++++++++++++++++++++++++++++++++ HackerRank:    / @hackerrankofficial   Tuschar Roy:    / tusharroy2525   GeeksForGeeks:    / @geeksforgeeksvideos   Jarvis Johnson:    / vsympathyv   Success In Tech:    / @successintech