运行 python 中使用 datetime 库的递归函数时间

Question

我在 python 中有 2 个函数可以使用 quicksort

对列表进行排序

import datetime
def partition(arr, low, high):
    i = (low - 1)  # index of smaller element
    pivot = arr[high]  # pivot

    for j in range(low, high):

        # If current element is smaller than or
        # equal to pivot
        if arr[j] <= pivot:
            # increment index of smaller element
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)

def quickSort(arr, low, high):
    dt_started = datetime.datetime.utcnow()

    if low < high:
        # pi is partitioning index, arr[p] is now
        # at right place
        pi = partition(arr, low, high)

        # Separately sort elements before
        # partition and after partition
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    dt_ended = datetime.datetime.utcnow()

    total_time = (dt_ended - dt_started).total_seconds()

    return total_time

其中 dt_started 是函数的开始时间，dt_ended 是结束时间。在我的 main 中，我这样调用函数：

total_time=quickSort(arr,0,n-1)

其中 arr 是我要排序的列表，n 是它的大小。

我的问题是，quickSort()函数return是否是正确的运行时间，因为在功能。

Answer 1

是的，会的。变量是函数的局部变量（在每次调用时），因此即使您递归调用函数，它们也不会被覆盖。

您可以通过在代码中放置一些痕迹来测试它。例如，您可以在代码中打印 dt_started 和 dt_ended 的值（我不打算讨论代码本身的作用）：

def quickSort(arr, low, high):
    print '>> called quickSort'
    print '  low:', low
    print ' high:', high
    dt_started = datetime.datetime.utcnow()
    print 'dt_started:', dt_started
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    print '> other calls finished'
    print '  low:', low
    print ' high:', high
    print 'dt_started:', dt_started        
    dt_ended = datetime.datetime.utcnow()
    print '  dt_ended:', dt_ended
    total_time = (dt_ended - dt_started).total_seconds()
    return total_time

运行这个函数用一个小数组：

In [4]: a = range(1,100)

In [5]: quickSort(a,0,1)
>> called quickSort
  low: 0
 high: 1
dt_started: 2019-03-26 14:59:41.840875
>> called quickSort
  low: 0
 high: 0
dt_started: 2019-03-26 14:59:41.840914
> other calls finished
  low: 0
 high: 0
dt_started: 2019-03-26 14:59:41.840914
  dt_ended: 2019-03-26 14:59:41.841138
>> called quickSort
  low: 2
 high: 1
dt_started: 2019-03-26 14:59:41.841253
> other calls finished
  low: 2
 high: 1
dt_started: 2019-03-26 14:59:41.841253
  dt_ended: 2019-03-26 14:59:41.841327
> other calls finished
  low: 0
 high: 1
dt_started: 2019-03-26 14:59:41.840875
  dt_ended: 2019-03-26 14:59:41.841370
Out[5]: 0.000495

如您所见，调用末尾的 dt_started 与第一个调用相同。它保留它在第一次调用时的值，并且总计算时间将是正确的。

运行 python 中使用 datetime 库的递归函数时间

Running time of recursive function using datetime library in python

python

recursion

time

quicksort