Всичко, което трябва да знаете за „Big O Notation“, за да пропуснете следващото си интервю за кодиране

Като част от образованието си за разработка на софтуер, трябваше да изградя умения в различни области, за да се подготвя напълно за първата си софтуерна позиция. И всяка програма за обучение по софтуер, която си заслужава, ще включва справедлива част от учебната програма, насочена към подготовката за скандалното интервю за кодиране.

Така че за тази цел, в началото на всеки един ден, работя върху решаването на алгоритми, тъй като това е основна част (и за мнозина най-трудната част ) от повечето интервюта за кодиране.

Едно нещо, с което съм се сблъсквал по време на работата по алгоритмите по компютърни науки, е нещо, наречено „Big O Notation“ .

Това е доста абстрактна и много езотерична концепция, за която по-голямата част от хората никога няма да чуят или да се интересуват. НО той е известен като често срещан въпрос за интервю за кодиране и следователно това е едно от нещата, за които прекарах известно време.

Какво трябва да знаете

Ето какво усвоих, за да се подготвя

За да зададем сцената за „Big O“, първо трябва да признаем, че софтуерът, разбира се, се основава силно на данни . Огромни планини от данни. И използването на тези данни е предназначението на кодирането. За да може дадена програма да използва данни, тя често трябва да започне чрез сортиране на тези данни в логически ред. Дали това е по азбучен ред, хронологично, по размер, по дата и т.н.

Сортирането се извършва ПОСТОЯННО и всъщност представлява огромна част от цялата компютърна и интернет дейност. Чувал съм програмисти да твърдят, че „Бързото сортиране е почти това, което управлява целия Интернет“.

Какво имат предвид под това? Данните за сортиране на кладенци са целият му подраздел в рамките на изучаването на компютърните науки и има много добре дефинирани алгоритми за сортиране. Има бързо сортиране, сортиране на балончета, сортиране по избор, сортиране по обединяване, сортиране на купчини и много други. Всеки с различни подходи, за да стигне до едни и същи или подобни резултати.

Но кой е най-добрият, ако всички (почти) всички върнат един и същ резултат?

Най-доброто обикновено означава кое е най-бързо. Тук влезе в игра “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“ рейтинг от O (n ^ 4).

Когато разглеждаме много от най-често използваните алгоритми за сортиране,рейтингът на O (n log n) като цяло е най-доброто, което може да се постигне. Алгоритмите, които се изпълняват при този рейтинг, включват бързо сортиране, сортиране на купчина и сортиране на обединяване. Бързото сортиране е стандартно и се използва по подразбиране на почти всички езици на софтуера.

Важно е да се отбележи, че няма нито един алгоритъм, който да е най-бърз във всички случаи , тъй като данните могат да се въвеждат в програма по всички начини на състояния. И подходите на всеки алгоритъм ще имат най-добрия и най-лошия сценарий, когато те се представят в най-добрия или най-лошия си случай.

Докато Quick Sort е стандарт, той също се конкурира с Merge Sort и Heap Sort, които са други алгоритми за сортиране с оценка O (n log n). Има сценарии, при които те се използват вместо това.

Най-прекият конкурент на Quick Sort е Heap Sort. Времето за работа на Heap Sort също е O (n log n), но средното време за работа на Heap Sort обикновено се счита за по-бавно от бързото сортиране на място.

Merge Sort е стабилно сортиране , което означава, че запазва реда на въвеждане на равни елементи в изхода, за разлика от стандартното бързо сортиране на място и Heap Sort.

Bubble / Insertion / Selection Sort се изпълнява при O (n²) , което от гледна точка на броя на операциите може да отнеме значително повече време от изброените по-горе с оценка O (n log n), когато се работи с наистина големи данни. Но може да има сценарии, при които другите да са по-бързи в зависимост от данните.

Има и моменти, в които нещо, което е много просто, като Counting Sort, е чудесно, защото е много по-бързо да се напише и много по-лесно да се визуализира и разбере.

Понякога не само трябва да вземете предвид изискванията за време на даден алгоритъм, но също така и изискванията за пространство на данни (или може би дори повече). Някои алгоритми работят и с по-малък отпечатък.

Защо трябва да знаете всичко това?

Така че след всичко това, ако винаги просто прибягвате до използването на вградения в езика алгоритъм за сортиране (който се основава на Бързо сортиране), тогава защо да се интересувате от алгоритмите за сортиране и „Big O“? Защо компаниите ще ви питат за това в интервю?

Отговорът е, че изучаването на нотация на Big O ви кара да разберете много важната концепция за ефективност във вашия код. Така че, когато работите с огромни масиви от данни, ще имате добра представа къде големите забавяния вероятно ще доведат до затруднения и къде трябва да се обърне повече внимание, за да се постигнат най-големи подобрения. Това се нарича още анализ на чувствителността и е важна част от решаването на проблеми и писането на страхотен софтуер.

Така че, ако се опитвате да се подготвите за първото си интервю или може би сте се борили в последното си, увеличаването на знанията ви по понятия като Big O Notation и други теми по компютърни науки ще ви помогне да се откажете. Ще бъдете по-добре подготвени да демонстрирате своя потенциал и да впечатлите, за да качите тази позиция.