У меня есть два алгоритма: A() и B().Они выполняют некоторое количество арифметических операций:
A():
- n-1 сложений
- n вычитаний
B():
- n-1 сложения
- n вычитания
- n квадраты (степень 2)
- 1 квадратный корень (степень 1/2)
Я широко определилA() выполняет 2n-1 операции и B() выполняет 3n операции.Если вам интересно, A() и B() вычисляют расстояния между точками в n-пространстве, используя прямолинейные и евклидовы метрики соответственно.
Как я могу описать затраты времени выполнения каждого алгоритма?Как компьютер обрабатывает определенные арифметические операции?Скажем, сложение заняло 1 единицу времени, вычитание также.Но как насчет умножения или деления?Квадратный корень?
A() выполняет на ~ 33% меньше операций, чем B(), но это не может описать время выполнения каждой из них.Как я могу наилучшим образом приблизить время выполнения каждого к n?Я могу с уверенностью предположить, что A() на 33% быстрее, чем B(), но это слово.