Сложность тестирования с использованием модуля времени

Question

У меня есть сомнения относительно сложности времени с рекурсией. Допустим, мне нужно найти наибольшее число в списке, используя рекурсию, вот что я придумал:

def maxer(s):
    if len(s) == 1:
        return s.pop(0)
    else:
        if s[0]>s[1]:
            s.pop(1)
        else:
            s.pop(0)
        return maxer(s)

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

import time
import matplotlib.pyplot as plt
def timer_v3(fx,n):
    x_axis=[]
    y_axis=[]
    for x in range (1,n):
        z = [x for x in range(x)]
        start=time.time()
        fx(z)
        end=time.time()
        x_axis.append(x)
        y_axis.append(end-start)
    plt.plot(x_axis,y_axis)
    plt.show() 

Есть ли принципиальный недостаток в проверке сложности, такой как грубая оценка? Если так, как мы можем быстро проверить сложность времени?

Answer 1

Если s является списком, то сложность времени вашей функции равна O (n ² ). Когда вы pop от начала списка, оставшиеся элементы должны быть сдвинуты влево на один пробел, чтобы «заполнить» пробел; это занимает O (n) времени, и ваша функция появляется из начала списка O (n) раз. Таким образом, общая сложность O (n * n) = O (n ² ).

---

Ваш график не выглядит как квадратичный c функция, хотя, потому что определение O (n ² ) означает, что оно должно иметь квадратичное c поведение только для n> n ₀ , где n ₀ - произвольное число. 1,000 не очень большое число, особенно в Python, потому что время выполнения для меньших входных данных в основном связано с издержками интерпретатора, а операция O (n) pop на самом деле очень быстрая, потому что она записана в C. Таким образом, это не только возможно, но вполне вероятно, что n <1000 слишком мало, чтобы наблюдать поведение quadrati c. </p>

Проблема в том, что ваша функция рекурсивна, поэтому ее не обязательно запускать для достаточно больших входов, чтобы соблюдайте квадратичность c времени работы. Слишком большие входы переполняют стек вызовов или используют слишком много памяти. Поэтому я преобразовал вашу рекурсивную функцию в эквивалентную итеративную функцию, используя while l oop:

def maxer(s):
    while len(s) > 1:
        if s[0] > s[1]:
            s.pop(1)
        else:
            s.pop(0)
    return s.pop(0)

Это строго быстрее, чем рекурсивная версия, но с той же временной сложностью. Теперь мы можем go гораздо дальше; Я измерил время работы до n = 3 000 000

1025 *

Это очень похоже на квадратичную c функцию. В этот момент у вас может возникнуть соблазн сказать: "ах, @ kaya3 показала мне, как правильно выполнять анализ, и теперь я вижу, что функция - это O (n ² )." Но это все еще неправильно. Измерение фактического времени работы - то есть динамический c анализ - все еще не является правильным способом анализа временной сложности функции. Сколько бы n мы ни тестировали, n ₀ могло бы быть еще больше, и у нас не было бы возможности узнать.

Так что, если вы хотите найти временную сложность алгоритма, у вас есть сделать это с помощью stati c анализ , как я (грубо) сделал в первом абзаце этого ответа. Вы не экономите время, выполняя динамический анализ c; чтение вашего кода и проверка того, что он выполняет операцию O (n) O (n) раз, если у вас есть знания, занимает менее минуты. Так что, безусловно, стоит развивать эти знания.