Прохожу собеседование в одну компанию. Дошел до 3 этапа - собеседование на знание алгоритмов и БД. Но есть проблема, я ни как не вкурю методику big O. Я понимаю для чего это и как потенциально это работает, но я не понимаю как самому вычислить алгоритмическую сложность. Кто может популярно объяснить, как рассчитывать?
_____________
Люди, имеющие низкий уровень квалификации, делают ошибочные выводы, принимают неудачные решения и при этом неспособны осознавать свои ошибки в силу низкого уровня своей квалификации
Полная Версия: big O
Вообще не слышал про такое 
, будет тоже интересно послушать.
, будет тоже интересно послушать.
Про вычисление сложности нашел это https://www.youtube.com/watch?v=z2YDoNV4FM4
_____________
Люди, имеющие низкий уровень квалификации, делают ошибочные выводы, принимают неудачные решения и при этом неспособны осознавать свои ошибки в силу низкого уровня своей квалификации
_____________
Люди, имеющие низкий уровень квалификации, делают ошибочные выводы, принимают неудачные решения и при этом неспособны осознавать свои ошибки в силу низкого уровня своей квалификации
Вот еще можно глянуть.
А если совсем популярно -- то рассчитывается так:
Если твой алгоритм не зависит от набора данных -- это O(1) (работает за константное время).
Если твоему алгоритму нужно пройтись по набору данных 1 раз от начала и до конца -- то это O(n); (то есть один цикл for i=0; i<data.length; i++) {...})
Если у тебя вложенные циклы -- то O(n^2), O(n^3) и тд, в зависимости от количества вложенных циклов.
Если нужно пройтись только по части данных -- то это уже меньше чем O(n). Например, бинарный поиск -- O(log(n)).
Ну и если у тебя комбинации этих проходов -- то O(n) перемножаются.
_____________
Чатик в телеге
А если совсем популярно -- то рассчитывается так:
Если твой алгоритм не зависит от набора данных -- это O(1) (работает за константное время).
Если твоему алгоритму нужно пройтись по набору данных 1 раз от начала и до конца -- то это O(n); (то есть один цикл for i=0; i<data.length; i++) {...})
Если у тебя вложенные циклы -- то O(n^2), O(n^3) и тд, в зависимости от количества вложенных циклов.
Если нужно пройтись только по части данных -- то это уже меньше чем O(n). Например, бинарный поиск -- O(log(n)).
Ну и если у тебя комбинации этих проходов -- то O(n) перемножаются.
_____________
Чатик в телеге
| Цитата (brevis @ 16.09.2017 - 09:40) |
| Если твоему алгоритму нужно пройтись по набору данных 1 раз от начала и до конца -- то это O(n); (то есть один цикл for i=0; i<data.length; i++) {...}) |
Не обязательно, у меня могут быть и вложенные циклы, но при этом сложность будет O(n). O(n) лишь "сообщает", что при росте входных данных n мы будем иметь линейный рост.
_____________
Mysql, Postgresql, Redis, Memcached, Unit Testing, CI, Kohana, Yii, Phalcon, Zend Framework, Joomla, Open Cart, Ymaps, VK Api
То что вы объясняете я и так уже понял.
_____________
Люди, имеющие низкий уровень квалификации, делают ошибочные выводы, принимают неудачные решения и при этом неспособны осознавать свои ошибки в силу низкого уровня своей квалификации
_____________
Люди, имеющие низкий уровень квалификации, делают ошибочные выводы, принимают неудачные решения и при этом неспособны осознавать свои ошибки в силу низкого уровня своей квалификации
Глянь сюда http://bigocheatsheet.com/
Поправьте, если ошибаюсь, но оценка сложности алгоритма имеет смысл только на больших входных данных? То есть какая-то обработка, скорее всего около big data направления.
Есть еще вот такое видео: https://www.youtube.com/watch?v=V6mKVRU1evU
В комментах по ссылке, которую дал Oyeme оно тоже присутствует.
Есть еще вот такое видео: https://www.youtube.com/watch?v=V6mKVRU1evU
В комментах по ссылке, которую дал Oyeme оно тоже присутствует.
| Цитата (Ron @ 17.09.2017 - 14:39) |
| Поправьте, если ошибаюсь, но оценка сложности алгоритма имеет смысл только на больших входных данных? То есть какая-то обработка, скорее всего около big data направления. |
Нет. Понимание сложности позволяет оценить сложность и найти более эффективное решение.
Например, если я возьму следующий алгоритм вычисления числа Фибоначчи:
function fibonacci($n)
{
if ($n < 3) {
return 1;
}
else {
return fibonacci($n-1) + fibonacci($n-2);
}
}
То с первого взгляда, отложу его подальше, т-к такой алгоритм, чудовищно медленный и стремится к O(n!). Даже вычисление 100-го числа Фибоначчи для такого алгоритма, при использовании всех вычислительных мощностей на планете, займет миллиарды лет.
_____________
Mysql, Postgresql, Redis, Memcached, Unit Testing, CI, Kohana, Yii, Phalcon, Zend Framework, Joomla, Open Cart, Ymaps, VK Api
T1grOK, очень наглядный пример! Только для данного алгоритма, по-моему, будет не n!, а 2^n. Но он от этого сильно лучше не становится.
Чем больше изучаю базовые алгоритмы и структуры данных, тем больше понимаю, что их нужно знать любому программисту.
_____________
Люди, имеющие низкий уровень квалификации, делают ошибочные выводы, принимают неудачные решения и при этом неспособны осознавать свои ошибки в силу низкого уровня своей квалификации
_____________
Люди, имеющие низкий уровень квалификации, делают ошибочные выводы, принимают неудачные решения и при этом неспособны осознавать свои ошибки в силу низкого уровня своей квалификации
| Цитата (chee @ 19.09.2017 - 22:32) |
| Чем больше изучаю базовые алгоритмы и структуры данных, тем больше понимаю, что их нужно знать любому программисту. |
Предлагаю спросить твина, согласен ли он с алгоритмами
Может он скажет, что в вебе они не нужны Ну а чё, холиварчик по ООП вы провели, холиварчик по паттернам уже как-то сливается... Народ требует зрелищ
_____________
Свои мозги еще никто не отменял.
Телепатов нету.
| Цитата (waldicom @ 20.09.2017 - 10:22) |
| Предлагаю спросить твина, согласен ли он с алгоритмами Может он скажет, что в вебе они не нужны Ну а чё, холиварчик по ООП вы провели, холиварчик по паттернам уже как-то сливается... Народ требует зрелищ |
Холиварчик по алгоритмам -- это был бы шаг назад. После ооп и паттернов надо проводить холиварчик по ФП там... (и что-то мне подсказывает интуиция, что в обозримом будущем, когда на всяких там Хабрах наберется критическая масса статеек на эту тему, холиварчик таки состоится
).
_____________
Чатик в телеге
| Цитата (brevis @ 20.09.2017 - 07:40) |
| Холиварчик по алгоритмам -- это был бы шаг назад. |
Вообще-то в холиварчиках тема не важна. Важно что оппоненты с пеной на губах доказывают, что другая сторона, они как бы совсем немного очень сильно тупые ослы
Так что даешь холиварчиков разных и всяких. Прикольно на чуваков смотреть, как они " в интернете кто-то не прав" принцип подтверждают
_____________
Свои мозги еще никто не отменял.
Телепатов нету.
brevis
waldicom
Для начала нужно понять на какую тему лучше начать холиварчик, для этого нужно провести холиварчик на тему "лучшая тема для холиварчика", и тут же появятся холиварчики на темы "что такое холиварчик", "нужны ли холиварчики форумчанам", "стоит ли начинать свой холиварчик или ввязаться в готовый"
_____________
Промокод предоставляет скидку на заказ домена и/или хостинга reg.ru
BFCC-3895-8804-9ED2
waldicom
Для начала нужно понять на какую тему лучше начать холиварчик, для этого нужно провести холиварчик на тему "лучшая тема для холиварчика", и тут же появятся холиварчики на темы "что такое холиварчик", "нужны ли холиварчики форумчанам", "стоит ли начинать свой холиварчик или ввязаться в готовый"
_____________
Промокод предоставляет скидку на заказ домена и/или хостинга reg.ru
BFCC-3895-8804-9ED2
Здесь расположена полная версия этой страницы.