Алгоритм — это конечная, четко определённая последовательность шагов, которая преобразует входные данные в требуемый результат. Мы оцениваем его по двум критериям: correctness (всегда ли он дает правильный ответ?) и efficiency (сколько времени и памяти он использует?).
Действительный алгоритм должен быть (каждый шаг ясен), (завершаться) и производить результат для каждого допустимого входа.
# Find the maximum value in a list
def find_max(nums):
if not nums:
return None # handle empty input
largest = nums[0] # assume first is the max
for n in nums[1:]: # scan the rest
if n > largest:
largest = n # update when we see something bigger
return largest
find_max([3, 9, 2, 7]) # -> 9
Это посещает каждый элемент один раз.
Одна и та же задача, много алгоритмов с разными затратами. Всегда проверяйте граничные случаи (пустой ввод, один элемент, дубликаты) — именно там обычно нарушается correctness.
Алгоритмы — это основа решения задач в программном обеспечении.
Две программы могут давать одинаковый результат, но одна работает в тысячи раз быстрее.
Думать в терминах correctness и efficiency — вот что отличает код, работающий на тестовом примере, от кода, работающего в масштабе.
Это также общий язык технических интервью и обсуждений архитектуры систем.
Библиотека вопросов для IT-собеседований с подробными ответами — от Junior до Senior.
Поддержать