Я начал искать свою первую работу в сфере технологий после окончания учебного лагеря по программированию. Я создал несколько проектов и решил «проблемы кодирования», и когда мой код заработал, я был горд и пошел дальше. Оказывается, когда я начинаю готовиться к техническим проблемам (область, в которой мне уже нужно совершенствоваться), решения проблемы недостаточно. Пространство и время на кону. Если ваша программа решена методом «грубой силы», с достаточным количеством данных ваша программа будет медленной и хромой. Чтобы лучше подготовиться к техническим интервью, я изучил нотацию Big O, и каждое ее объяснение, казалось бы, сформулировано… слишком сложно? Это будет моя попытка превратить нотацию Big O во что-то, что человек сможет прочитать и понять.
Что такое нотация Big O? Почему?
Кажется, это хорошее место для начала. В программировании существует бесконечное количество способов решения проблемы. Допустим, у нас есть реальная жизненная проблема: вам нужно что-то дать своему соседу. Есть много сценариев, когда предмет может оказаться в их доме. Вы можете отправить его им по почте, но, вероятно, быстрее просто пройти по соседству и вручить им письмо. Этому я научился на собственном горьком опыте с программированием.
То, что ваш код работает, не означает, что он сделан.
Когда вы разрабатываете приложение и решаете проблему, вы должны найти наиболее эффективное решение. Мы находим наиболее эффективное решение с помощью нотации Big O и представляем, что наш код должен пройти 1 миллиард фрагментов данных.
Большой О
Здесь я пройдусь по «лейблам» Big O. Мне нравится думать о них как о ярлыках, которые в основном говорят: «Эта функция — ЭТА скорость».
Некоторая лексика, которую нам нужно понять:
n: размер ввода. Мне нравится думать, что n означает количество вещей, подключаемых к решению.
Основные действия компьютера: операции, которые должен выполнять компьютер. Это может быть сложение, вычитание, присвоение переменных и т. д.
Отбросьте константы для упрощения:это трудно объяснить сейчас, но позже в блоге будет показано. По сути, чтобы вычислить, какую метку мы даем алгоритму, мы просто смотрим на общую картину и в конце отбрасываем целые числа, которые не имеют значения. примеры ниже.
метки в порядке от самой быстрой к самой медленной
O(1) или постоянное время
Мы обозначаем что-то как O(1), когда решение вообще не требует n (ввод). Решение всегда будет иметь одни и те же компьютерные шаги.
пример:
x = 1 + 1
С помощью этого алгоритма мы всегда будем добавлять один раз и присваивать значение x один раз. Это не зависит ни от какого количества данных. Скажем, у нас есть несколько строк кода. Вы складываете строки вместе, а затем «игнорируете константы».
x = 1 + 1 //Big O(1) y = 2 + 1 //This one is Big O(1) as well z = x + y //Also Big O(1)
Для расчета мы добавим метки вверх O (1) + O (1) + O (1), чтобы получить 3 * O (1). Здесь мы «игнорируем константу». Нас не волнует, что есть 3 вещи, которые срабатывают невероятно быстро в сочетании с дополнением. Весь алгоритм за O(1). и это единственное, что важно в конце
O(n) или линейное время
Мы используем эту метку для алгоритма, который использует базовые компьютерные шаги, но эти шаги повторяются столько раз, сколько вы используете n. Основным примером этого является зацикливание и итерация данных.
пример:
Если бы мы хотели перебрать наше n и выполнять компьютерные шаги каждый раз, когда n равно 1000, мы бы выполнили компьютерные шаги 1000 раз. Если бы n было равно 1 миллиарду, мы бы выполнили эти шаги 1 миллиард раз. Ключевым выводом здесь является количество шкал времени, синхронизированных с любым количеством входных данных или n, которые мы используем.
//Pseudocode for every number in 0 to n 1 + number end
Как вы можете видеть, количество раз, которое ваш компьютер должен выполнить 1 + число, зависит от того, сколько n мы вводим. Важно отметить, что с петлями мы умножаем, а не складываем, как раньше. Теперь обратите внимание, что внутри цикла мы теперь знаем, что «1 + число» равно O (1) из предыдущего. Когда мы объединяем их, получается n*O(1) или просто O(n). Еще один пример O(n)
//Pseudocode friends = 0 //Big O(1) for every person in n //Big O(n) friends + 1 // end
Сумма представляет собой сумму этих двух алгоритмов, поэтому O (1) + O (n). O (1) не имеет значения для скорости этого решения, в конце концов, мы просто отбрасываем его как константу, чтобы просто дать нам простую метку O (n).
O(n²) или квадратичное время
Это будет последняя этикетка, которую я описываю в этом блоге. В основном это происходит, когда вы зацикливаетесь внутри цикла, и этого следует избегать, если это возможно. При работе с небольшим объемом данных вы не заметите, насколько медленными могут быть эти решения, потому что компьютеры очень мощные. Однако, когда вы начнете работать с большими n, ваше решение быстро выйдет из-под контроля. Лучший способ объяснить словами O(n²) — это следующий пример: скажем, вы устраиваете вечеринку и хотите узнать имена всех и чтобы все они также знали имена всех. O (n²) способ справиться с этим будет заключаться в том, чтобы сказать каждому человеку здесь (n), начиная по одному, спрашивать каждого человека здесь, (n) их имя, когда вы закончите, переходите к следующему человеку, тогда они спрашивают всех в партии их имена. Если вы похожи на меня и на вашей вечеринке всего 3 человека, это не так уж и плохо, но если у вас 100 человек или 239582305 человек, это будет худшая вечеринка. Старайтесь избегать этих решений.
пример:
//Pseudocode for number in 0 to n //O(n) for otherNumber in 0 to n //O(n) number + otherNumber
Как я упоминал ранее, внутри циклов мы умножаем метки вместе, поэтому мы будем делать O(n) * O(n) или просто O(n²).
Последние мысли
Это всего лишь 3 основных ярлыка, и я планирую продолжать учиться и писать более эффективный код для своих проектов и будущего работодателя.
Этот блог фокусируется на скорости и времени, а не на пространстве для краткости.
Я просто хотел привести еще несколько примеров вырезания «констант»:
O(2n) = O(n)
O(500) = O(1)
O(13n²) = O(n²)
Вот график, показывающий скорость работы этих меток: чем ниже линия, тем она быстрее.
Спасибо за прочтение и удачи в решении вашей проблемы!
