Используете ли вы оценку сложности Big-O в «реальном мире»? - PullRequest
16 голосов
/ 08 августа 2009

Недавно в одном из интервью мне задали несколько вопросов, связанных с Big-O различных алгоритмов, которые возникли в ходе технических вопросов. Я не думаю, что у меня это получилось очень хорошо ... За десять лет, прошедших с тех пор, как я прошел курсы программирования, где нас просили вычислить Big-O алгоритмов, у меня не было ни одного разговора о Big-O чего-либо Я работал или разработал. Я участвовал во многих дискуссиях с другими членами команды и с архитекторами, с которыми работал, по поводу сложности и скорости кода, но я никогда не был частью команды, которая фактически использовала вычисления Big-O в реальном проекте. Обсуждения всегда "есть ли лучший или более эффективный способ сделать это, учитывая наше понимание наших данных?" Никогда "какова сложность этого алгоритма"?

Мне было интересно, действительно ли люди обсуждают "Big-O" своего кода в реальном слове?

Ответы [ 11 ]

1 голос
/ 08 августа 2009

Хотя вам редко требуется глубокий анализ кода, важно знать, что это значит, и уметь быстро оценивать сложность кода, который вы пишете, и последствия, которые он может иметь.

Во время разработки вы часто чувствуете, что это "достаточно хорошо". Эх, никто никогда не поместит более 100 элементов в этот массив, верно? Затем, однажды, кто-то поместит 1000 элементов в массив (доверяйте пользователям: если код позволяет, один из них сделает это). И тот алгоритм n ^ 2, который был достаточно хорош сейчас, является большой проблемой производительности.

Иногда это бывает полезно с другой стороны: если вы знаете, что вам функционально необходимо выполнить n ^ 2 операций, а сложность вашего алгоритма равна n ^ 3, возможно, вы можете что-то с этим сделать, чтобы сделать n ^ 2. После n ^ 2 вам придется работать над меньшими оптимизациями.

Напротив, если вы только что написали алгоритм сортировки и обнаружили, что он имеет линейную сложность, вы можете быть уверены, что с ним есть проблема. (Конечно, в реальной жизни случаи, когда вам приходилось писать собственный алгоритм сортировки, редки, но однажды я увидел кого-то в интервью, кто был явно удовлетворен его единственным алгоритмом сортировки по циклам).

...