Эмпирическая оценка временной сложности алгоритма с использованием алгоритма градиентного спуска

Зачем оценивать временную сложность алгоритмически

Полезно оценить временную сложность алгоритма. Если вы знаете временную сложность алгоритма, вы знаете, насколько хорошо он будет работать, если вы предоставите ему большой объем данных.

Традиционно мы оценивали временную сложность алгоритмов теоретически. Это интересно с точки зрения информатики, поскольку помогает нам находить лучшие алгоритмы и строго расширять границы области без необходимости запуска большого количества дорогостоящих тестов.

Большинство инженеров-программистов оценивают временную сложность интуитивно. Например:

• Если алгоритм имеет цикл от 0 до n, то его временная сложность составляет O(n);
• Если алгоритм имеет k вложенных циклов, то его временная сложность составляет O(n^k);
• Если алгоритм является рекурсивным и генерирует дерево, то мы знаем, что нужно искать O(log(n)) и O(n * log (n)) временные сложности.

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

При столкновении с этими алгоритмами теоретические и интуитивные подходы становятся нежизнеспособными. Вот почему алгоритмический метод полезен.

Оценка временной сложности с использованием градиентного спуска

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

Большая нотация O представляет собой асимптотический рост времени вычислений с течением времени.

Например, рассмотрим алгоритм, который растет с O(n²). Пусть время, необходимое для вычисления алгоритма для заданного размера входных данных, определяется как: t(n) = a * n², где n — размер набора данных. Асимптотический рост алгоритма равен O(t(n)) = O(a * n²) = O(n²). Термины a и b игнорируются в большой нотации O, поскольку мы учитываем только то, как растет время вычислений. время, а не его точное значение во времени.

Я упомянул, что мы будем сравнивать измеренное время вычислений с набором известных функций роста. Вот несколько примеров таких общеизвестных функций роста:

• t(n) = a, где a — константа;
• t(n) = a * n + b, где a и b — константы, а n — входные данные. размер;
• t(n) = a * n^k + b, где a, b и k — константы и n — размер ввода;
• t(n) = a * b^n + b, где a, b и c — константы, а n — размер ввода;
• t(n) = a *log(n)+ b, где a и b — константы, а n — размер ввода;
• t(n) = a * n *log(n) + b, где a и b — это константы, а n — размер ввода.

Обратите внимание, что эти функции имеют постоянные параметры и изменение этих параметров изменит значения функций. Поскольку большая нотация O игнорирует эти параметры, при оценке разницы между измеренным временем вычислений и этими известными функциями мы должны сначала найти значения параметров, которые лучше всего соответствуют нашим измерениям. Здесь вступает в действие часть градиентного спуска. Мы изучим неизвестные параметры с помощью градиентного спуска, а затем сравним предсказанные значения с реальными значениями, которые мы измерили.

Измерение времени вычисления алгоритма для разных размеров входных данных

Первым шагом является сбор измерений времени, необходимого для запуска алгоритма для различных размеров входных данных.

Вот реализация таймера на Python, которую вы можете использовать для измерения времени выполнения алгоритма:

class ExecutionTimer:
    def __init__(self) -> None:
        self.start_timestamp = None
        self.stop_timestamp = None

        self.cumulative_exec_time = 0
        self.nb_iterations = 0

    def start(self) -> None:
        self.start_timestamp = time.time()

    def lap(self) -> None:
        self.stop_timestamp = time.time()

        exec_time = self.stop_timestamp - self.start_timestamp
        self.cumulative_exec_time += exec_time

        self.nb_iterations += 1
        self._end_iteration()

    def get_average_execution_time(self):
        average_exec_time = self.cumulative_exec_time / self.nb_iterations
        return average_exec_time

    def reset(self):
        self._end_iteration()
        self.cumulative_exec_time = 0
        self.nb_iterations = 0
    
    def _end_iteration(self):
        self.exec_start_timestamp = None
        self.stop_timestamp = None

Вот как вы будете собирать среднее время выполнения вашего алгоритма для нескольких входных размеров:

# You want to find the time complexity of this algorithm
def your_algorithm(input_data: list):
  ...

# Here is how:
# Prepare a timer to measure the execution time
timer = ExecutionTimer()

# Prepare inputs for many input sizes
# Here we pretend inputs[n][i] is a valid input of size n and that i is an instance number
# We generate multiple instances of each input size to get an average
inputs = [[...] for ...]

# Set boundaries for the input size
min_n = 2
max_n = 8

# Set the number of instances to use for the average
nb_instances = 5

# Prepare a list to store the execution times we measure
execution_times = []

# Run your algorithm multiple times for each input size to get an average
for n in range(min_n, max_n + 1):
  for i in range(nb_instances):
    timer.start()
    your_algorithm(inputs[n][i])
    timer.lap()

  avg_execution_time = timer.get_average_execution_time()
  execution_times.append((n, avg_execution_time))
  timer.reset()

Теперь у нас есть среднее время выполнения для входных данных размером от 2 до 8 в переменной execution_times.

Изучение неизвестных параметров известных функций времени вычислений

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

Во-первых, давайте определим общий базовый класс Regressor. Этот класс определяет несколько ключевых методов, которые будут использоваться для градиентного спуска:

• get_score(self, datapoints): вычисляет среднеквадратичную ошибку (MSE) между заданным набором данных и текущими прогнозами регрессора;
• _get_error(self, datapoint): вычисляет ошибку между заданной точкой данных наземной истины и текущим прогнозом регрессора для этого входа;
• _regress(self, get_parameter, set_parameter, datapoints, learning_rate) : реализация алгоритма градиентного спуска в стиле черного ящика. Он вычисляет производную ошибки, слегка изменяя заданный параметр в положительном и отрицательном направлениях и сравнивая результаты. Этот метод является более дорогостоящим, чем подход белого ящика, в котором мы заранее знали бы частную производную каждого параметра и не должны были бы оценивать функцию много раз. Однако метод «черного ящика» дает нам большую общность, и поскольку функции роста, которые мы оцениваем (т. е. t(n) = a * n²), выполняются очень быстро, прирост производительности метода «белого ящика» незначителен. .

class Regressor:
    def __init__(self) -> None:
        self.nb_iterations = 500

    def get_name(self):
        pass

    def fit(self, datapoints):
        pass

    def predict(self, x):
        pass

    def get_score(self, datapoints):
        cumulative_error = 0
        for datapoint in datapoints:
            cumulative_error += self._get_error(datapoint) ** 2
        return math.sqrt(cumulative_error)

    def _get_error(self, datapoint):
        (x, y) = datapoint
        return y - self.predict(x)
    
    def _regress(self, get_parameter, set_parameter, datapoints, learning_rate):
        base_parameter = get_parameter()
        neutral_score = self.get_score(datapoints)

        set_parameter(base_parameter + self.learning_rate)
        positive_score = self.get_score(datapoints)

        set_parameter(base_parameter - self.learning_rate)
        negative_score = self.get_score(datapoints)

        set_parameter(base_parameter)

        if positive_score >= negative_score and positive_score >= neutral_score:
            set_parameter(base_parameter - self.learning_rate)
        elif negative_score >= positive_score and negative_score >= neutral_score:
            set_parameter(base_parameter + self.learning_rate)

Затем давайте определим регрессоры для различных функций роста, которые мы хотим оценить:

Для t(n) = a :

class ConstantRegressor(Regressor):
    def __init__(self) -> None:
        super().__init__()
        self.constant = np.random.uniform(0, 5)
    
    def get_name(self):
        return "1"

    def fit(self, datapoints):
        self.constant = sum([y for (x, y) in datapoints]) / len(datapoints)
    
    def predict(self, x):
        return self.constant

Эта функция достаточно проста, поэтому нам не нужно использовать метод _regress, который мы определили в базовом классе Regressor. Все, что нам нужно сделать, чтобы соответствовать модели, это: a = mean(y).

Для t(n) = a * n :

class LinearRegressor(Regressor):
    def __init__(self) -> None:
        super().__init__()

        self.slope = np.random.uniform(0, 5)
        self.intercept = np.random.uniform(0, 5)
    
    def get_name(self):
        return "n"
    
    def fit(self, datapoints):
        local_slopes = [
            (datapoints[i + 1][1] - datapoints[i][1]) / (datapoints[i + 1][0] - datapoints[i][0])
            for i in range(len(datapoints) - 1)
        ]
        average_slope = sum(local_slopes) / len(local_slopes)

        self.slope = average_slope
        self.intercept = datapoints[0][1] - self.slope * datapoints[0][0]

    def predict(self, x):
        return self.slope * x + self.intercept

Этот регрессор также очень прост, мы выполняем простую линейную регрессию, чтобы соответствовать модели.

Для t(n) = a * n²:

class QuadraticRegressor(Regressor):
    def __init__(self) -> None:
        super().__init__()
        self.a = 0
        self.b = 0
        self.c = 0

        self.learning_rate = 0.0000005

    def get_name(self):
        return "n^2"
    
    def fit(self, datapoints):
        for _ in range(self.nb_iterations):
            for (x, y) in datapoints:
                self._regress(self._get_a, self._set_a, datapoints, self.learning_rate)
                self._regress(self._get_b, self._set_b, datapoints, self.learning_rate)
                self._regress(self._get_c, self._set_c, datapoints, self.learning_rate)

    def predict(self, x):
        return self.a + self.b * x + self.c * x ** 2
    
    def _get_a(self): return self.a
    def _set_a(self, a): self.a = a

    def _get_b(self): return self.b
    def _set_b(self, b): self.b = b

    def _get_c(self): return self.c
    def _set_c(self, c): self.c = c

Мы также могли бы выполнить простую квадратичную регрессию для этого, но вот пример того, как вы можете использовать мой общий метод _regress. Он вызывается несколько раз для каждого параметра модели.

Вы можете применить тот же принцип к другим функциям роста, которые мы представили. Все, что вам нужно сделать, это вычислить функцию роста в методе predict(self, x) и в методе fit(self, datapoints) вызвать метод _regress несколько раз для каждого параметра в функции роста.

Метод get_name(self) — это служебный метод, который позволяет легко распечатать временную сложность после того, как мы нашли наилучшее соответствие.

Поиск наилучшей подходящей функции временной сложности

Последний шаг — подобрать набор моделей к нашим измеренным данным и сравнить их прогнозы, чтобы найти наиболее подходящую модель.

Вот пример того, как вы могли бы обучить набор регрессоров на измеренном времени вычислений, которое мы получили в предыдущем разделе:

regression_scores = []
regressors = [
    ConstantRegressor(),
    LinearRegressor(),
    QuadraticRegressor()
]

for regressor in regressors:
    regressor.fit(execution_times)
    regression_scores.append(regressor.get_score(execution_times))

min_regression_score = min(regression_scores)
min_regression_score_index = regression_scores.index(min_regression_score)

best_regressor = regressors[min_regression_score_index]

print("The time complexity is: O(%s)" % best_regressor.get_name())

И вуаля! Если вы все сделали правильно, ваша программа напечатает большую нотацию O функции роста, которая лучше всего соответствует вашему алгоритму.

Теперь вы можете улучшить этот инструмент, добавив новые регрессоры, которые моделируют более сложные функции роста, чтобы он мог определять временную сложность более сложных алгоритмов.