Все, що вам потрібно знати про “Велику нотацію О”, щоб розбити ваше наступне співбесіду з кодування

В рамках навчання з розробки програмного забезпечення мені потрібно було набути навичок у різних сферах, щоб повністю підготуватися до моєї першої посади програмного забезпечення. І будь-яка навчальна програма з програмного забезпечення, що коштує їх солі, включатиме неабияку частину навчальної програми, спрямованої на підготовку до сумнозвісного інтерв’ю з кодування.

Тому з цією метою, на початку кожного дня, я працюю над вирішенням алгоритмів, оскільки це основна частина (і багатьом найскладніша частина ) більшості інтерв’ю з кодування.

Одне, з чим я стикався під час роботи над алгоритмами інформатики, - це щось під назвою „Велике позначення О” .

Це досить абстрактна і дуже езотерична концепція, про яку переважна більшість людей ніколи не почує і не піклується про неї. АЛЕ це відоме як поширене запитання про співбесіду , і тому це одна з речей, про яку я витратив певний час, вивчаючи все.

Що потрібно знати

Ось те, що я поглинув, щоб підготуватися

Щоб встановити сцену для «Великого О», нам спочатку слід визнати, що програмне забезпечення, звичайно, значною мірою базується на даних . Величезні гори даних. І використання цих даних є тим, для чого призначене кодування. Для того, щоб програма використовувала дані, часто потрібно почати з сортування цих даних у логічний порядок. Будь то за алфавітом, хронологічно, за розміром, за датою тощо.

Сортування відбувається ПОСТІЙНО, і насправді становить величезну частину всієї діяльності на комп’ютері та в Інтернеті. Я чув, як програмісти стверджують, що "швидке сортування - це майже те, чим керує весь Інтернет".

Що вони мають на увазі під цим? Дані сортування свердловин - це весь його власний підрозділ у рамках вивчення інформатики, і існує безліч чітко визначених алгоритмів сортування. Існує швидке сортування, сортування за міхурами, сортування за виділенням, сортування за об’єднанням, сортування за купою та багато іншого. Кожен з різних підходів для досягнення однакових або подібних результатів.

Але який із них найкращий, якщо вони (майже) всі повернуть однаковий результат?

Найкраще зазвичай означає, що найшвидше. Тут у гру увійшов “Big O”.

Позначення Big O, яке іноді також називають «асимптотичним аналізом», насамперед розглядає, скільки операцій потрібно алгоритму сортування для повного сортування дуже великої колекції даних. Це показник ефективності, і це спосіб безпосереднього порівняння одного алгоритму з іншим.

При створенні простого додатка, на якому працює лише декілька даних, такий аналіз не потрібен. Але при роботі з дуже великими обсягами даних, як-от сайт соціальних медіа чи великий сайт електронної комерції з великою кількістю клієнтів та продуктів, незначні відмінності між алгоритмами можуть бути значними.

Позначення Big O оцінює ефективність алгоритмів

Це робиться стосовно " O " та " n " (приклад: " O (log n)") , де

  • O відноситься до порядку функції або швидкості її зростання, і
  • n - довжина масиву, що підлягає сортуванню.

Давайте попрацюємо на прикладі. Якщо алгоритм має кількість операцій, потрібна формула:

f (n) = 6n ^ 4 - 2n ^ 3 + 5

Оскільки « n » наближається до нескінченності (для дуже великих наборів даних), з усіх трьох присутніх термінів важливим є лише 6n ^ 4 . Отже, менші терміни, 2n ^ 3 і 5 , насправді просто опущені, оскільки вони незначні. Те саме стосується і « 6 » у 6n ^ 4 , насправді.

Отже, ця функція матиме темп зростання порядку або рейтинг “великого О” O (n ^ 4).

Розглядаючи багато найбільш часто використовуваних алгоритмів сортування,рейтинг O (n log n) загалом є найкращим, чого можна досягти. Алгоритми, що працюють за цим рейтингом, включають швидке сортування, сортування по купі та сортування за злиттям. Швидке сортування є стандартом і використовується за замовчуванням майже у всіх мовах програмного забезпечення.

Важливо зазначити, що не існує єдиного алгоритму, який би був найшвидшим у всіх випадках , оскільки дані можуть вводитися в програму за будь-яких манер станів. І підходи кожного алгоритму матимуть найкращий і найгірший сценарії, коли вони виконують свої найкращі або гірші результати.

Хоча швидке сортування є стандартом, воно також конкурує з об’єднаним сортуванням та сортуванням купи, що є іншими алгоритмами сортування за рейтингом O (n log n). Є сценарії, коли вони використовуються замість цього.

Найбільш прямим конкурентом Quick Sort є Heap Sort. Час роботи Heap Sort також становить O (n log n), але середній час роботи Heap Sort зазвичай вважається повільнішим, ніж швидке сортування на місці.

Сортування злиття - це стабільне сортування , що означає, що воно зберігає порядок введення рівних елементів у виведенні, на відміну від стандартного швидкого сортування на місці та купового сортування.

Сортування міхура / вставки / вибору виконується при O (n²) , що за кількістю операцій може зайняти значно більше часу, ніж перераховані вище, оцінені за O (n log n) при роботі з справді великими даними. Але можуть бути сценарії, коли інші швидші, залежно від даних.

Бувають також випадки, коли щось дуже просте, наприклад підрахунок сорту, є чудовим, оскільки це набагато швидше писати і набагато легше візуалізувати та розуміти.

Іноді вам потрібно не тільки врахувати вимоги часу до алгоритму, але й вимоги до простору даних (або, можливо, навіть більше того). Деякі алгоритми також працюють із меншим розміром сховища.

Навіщо вам все це знати?

Тож після всього цього, якщо ви завжди просто вдаєтесь до використання вбудованого в мову алгоритму сортування (який базується на Швидкому сортуванні), то навіщо тоді піклуватися про алгоритми сортування та “Big O”? Чому компанії запитують вас про це в інтерв’ю?

Відповідь полягає в тому, що вивчення позначення Big O змушує вас зрозуміти дуже важливу концепцію ефективності вашого коду. Отже, коли ви працюєте з величезними наборами даних, ви будете добре розуміти, де великі уповільнення можуть спричинити вузькі місця, і де слід приділяти більше уваги, щоб отримати найбільші вдосконалення. Це також називається аналізом чутливості і є важливою частиною вирішення проблем та написання чудового програмного забезпечення.

Отже, якщо ви намагаєтеся підготуватися до свого першого інтерв’ю, або, можливо, вам доводилося боротися на останньому, підвищення знань щодо таких понять, як Big O Notation та інших тем з інформатики, допоможе вам піднятися. Ви будете краще підготовлені, щоб продемонструвати свій потенціал і вразити, щоб приземлитися на цій позиції.