Здесь измерялось время, потраченное алгоритмом на обработку набора размером N. Представлены данные о самом быстром (потребовавшем меньше всего времени) решении среди всех попыток. Такой подход лучше обычного вычисления среднего времени по всем однотипным наборам данных, потому что в среднее может закрасться измерение, которое оказалось большим не по вине алгоритма.
Алгоритм — это пошаговая инструкция решения некоторой задачи, реализованная в виде программы.
Правильная функция, которая находит наибольшее значение в списке
Принято думать, что оценить эффективность алгоритма — значит подсчитать, сколько ему потребовалось вычислительных операций. Но как раз это совсем не просто! Центральный процессор компьютера (CPU) исполняет машинные инструкции — арифметические операции (наподобие сложения и умножения), пересылку данных из памяти в регистры процессора, сравнения и т.п.
Когда придумываешь алгоритм, важнее всего убедиться, что он работает правильно на всех допустимых наборах входных данных.
• Время вычисления max() на достаточно длинных возрастающих последовательностях всегда больше времени вычисления на таких же, но убывающих.
• Если длина последовательности увеличивается вдесятеро, время вычисления max() на ней тоже увеличивается плюс-минус вдесятеро, как если бы мы каждую проверку делали вручную.
Алгоритм — это пошаговая инструкция решения некоторой задачи, реализованная в виде программы. Программа должна возвращать правильный ответ за предсказуемое время. Изучая алгоритм, мы проверяем и правильность ответа (в том числе на всех допустимых входных данных), и его вычислительную сложность (возможно, есть более эффективные решения задачи).