рекурсия против временной сложности итерации

Question

Может ли кто-нибудь точно объяснить, что происходит под капотом, чтобы сделать рекурсивный подход в следующей задаче намного более быстрым и эффективным с точки зрения временной сложности?

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

Например:

• Вход: [22, 5, 3, 1, 8, 2]

• Вывод: [5, 8, 22]

Несмотря на то, что мы можем просто отсортировать исходный массив и вернуть последние три элемента, это займет не менее O(nlog(n)) time как самый быстрый алгоритм сортировки сделает именно это. Таким образом, задача состоит в том, чтобы выполнить задачу лучше и выполнить задачу за O(n) время.

Итак, я смог придумать рекурсивное решение:

def findThreeLargestNumbers(array, largest=[]):

    if len(largest) == 3:
        return largest

    max = array[0]
    for i in array:
        if i > max:
            max = i

    array.remove(max)
    largest.insert(0, max)
    return findThreeLargestNumbers(array, largest)

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

Однако, когда я посмотрел на предложенный итерационный метод, я составил этот код:

def findThreeLargestNumbers(array):
    sortedLargest = [None, None, None]
    for num in array:
        check(num, sortedLargest)
    return sortedLargest

def check(num, sortedLargest):
    for i in reversed(range(len(sortedLargest))):
        if sortedLargest[i] is None:
            sortedLargest[i] = num
            return
        if num > sortedLargest[i]:
            shift(sortedLargest, i, num)
            return

def shift(array, idx, element):
    if idx == 0:
        array[0] = element
        return array
    array[0] = array[1]
    array[idx-1] = array[idx]
    array[idx] = element
    return array

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

рекурсивный подход был намного быстрее (примерно в 9 раз быстрее), чем итерационный подход!

Почему так? Несмотря на то, что рекурсивный подход заключается в трехкратном обходе огромного массива и, вдобавок ко всему, каждый раз, когда он удаляет элемент (что занимает O(n) времени, поскольку все остальные 999 элементы должны быть перемещены в памяти), тогда как итерационный подход заключается в обходе входного массива только один раз, и да, выполнение некоторых операций на каждой итерации, но с очень незначительным массивом размера 3, который вообще не потребует времени!

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

Answer 1

Совет по оптимизации.

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

Ваш рекурсивный код выполняет только 3 вызова функций и, как указано в другом месте, выполняет в среднем 1,5 сравнения за вызов. (1 при поиске минимума, 0,5 при выяснении, где удалить элемент.)

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

Теперь сравните с этим итеративным решением:

def find_largest(array, limit=3):
    if len(array) <= limit:
        # Special logic not needed.
        return sorted(array)
    else:
        # Initialize the answer to values that will be replaced.
        min_val = min(array[0:limit])
        answer = [min_val for _ in range(limit)]

        # Now scan for smallest.
        for i in array:
            if answer[0] < i:
                # Sift elements down until we find the right spot.
                j = 1
                while j < limit and answer[j] < i:
                    answer[j-1] = answer[j]
                    j = j+1
                # Now insert.
                answer[j-1] = i

        return answer

Нет вызовов функций. Возможно, вы можете сделать до 6 сравнений на элемент (убедитесь, что answer[0] < i, убедитесь, что (j=1) < 3, убедитесь, что answer[1] < i, убедитесь, что (j=2) < 3, убедитесь, что answer[2] < i, затем найдите, что (j=3) < 3 это не правда). Вы попадете в худший случай, если будет отсортировано array. Но в большинстве случаев вы делаете только первое сравнение, а затем переходите к следующему элементу. Без суеты.

Как это тестируется?

Обратите внимание, что если вам нужны 100 наименьших элементов, вам стоит использовать более разумную структуру данных, такую ​​как куча , чтобы избежать пузырьковой сортировки.

Answer 2

Меня не очень устраивает python, но у меня другой подход к проблеме, чего бы он ни стоил. Насколько я видел, все опубликованные решения имеют вид O(N<em>M), где N - длина массива, а M - длина самого большого массива элементов. Из-за вашей конкретной c ситуации, когда N >> M вы могли бы сказать, что это O(N), но чем длиннее входы, тем больше будет O(N</em>M) Я согласен с @zvone, что, похоже, у вас есть больше шагов в итеративном решении, что звучит как действительное объяснение вашей разной скорости вычислений. Возвращаясь к моему предложению, реализует бинарный поиск O(N*logM) с рекурсией:

import math

def binarySearch(arr, target, origin = 0):
    """ 
    Recursive binary search
    Args:
        arr (list): List of numbers to search in
        target (int): Number to search with
    Returns:
        int: index + 1 from inmmediate lower element to target in arr or -1 if already present or lower than the lowest in arr
    """
    half = math.floor((len(arr) - 1) / 2);
    if target > arr[-1]:
        return origin + len(arr)
    if len(arr) == 1 or target < arr[0]:
        return -1
    if arr[half] < target and arr[half+1] > target:
        return origin + half + 1
    if arr[half] == target or arr[half+1] == target:
        return -1
    if arr[half] < target:
        return binarySearch(arr[half:], target, origin + half)
    if arr[half] > target: 
        return binarySearch(arr[:half + 1], target, origin)
    
def findLargestNumbers(array, limit = 3, result = []):
    """ 
    Recursive linear search of the largest values in an array
    Args:
        array (list): Array of numbers to search in
        limit (int): Length of array returned. Default: 3
    Returns:
        list: Array of max values with length as limit
    """    
    if len(result) == 0:
        result = [float('-inf')] * limit
    if len(array) < 1:
        return result
    val = array[-1]
    foundIndex = binarySearch(result, val)
    if foundIndex != -1:
        result.insert(foundIndex, val)
        return findLargestNumbers(array[:-1],limit, result[1:])
    return findLargestNumbers(array[:-1], limit,result)

Он довольно гибкий и может послужить источником вдохновения для более детального ответа.

Answer 3

Рекурсивное решение

Рекурсивная функция просматривает список 3 раза, чтобы найти наибольшее число, и 3 раза удаляет наибольшее число из списка.

for i in array:
    if i > max:
        ...

и

array.remove(max)

Итак, у вас есть 3 × N сравнений плюс 3-кратное удаление. Я предполагаю, что удаление оптимизировано в C, но опять же есть примерно 3 × (N / 2) сравнений, чтобы найти элемент, который нужно удалить.

Итак, всего примерно 4,5 × N сравнений.

Другое решение

Другое решение проходит по списку только один раз, но каждый раз сравнивается с тремя элементами в sortedLargest:

for i in reversed(range(len(sortedLargest))):
    ...

и почти каждым раз он сортирует sortedLargest с этими тремя присваиваниями:

array[0] = array[1]
array[idx-1] = array[idx]
array[idx] = element

Итак, вы N раз:

• вызов check
• создание и изменение a range(3)
• доступ sortedLargest[i]
• сравнение num > sortedLargest[i]
• вызов shift
• сравнение idx == 0

и примерно 2 × N / 3 раза, делая:

array[0] = array[1]
array[idx-1] = array[idx]
array[idx] = element

и N / 3 раза array[0] = element

Трудно посчитать, но это намного больше, чем 4,5 × N сравнений.