具有两个调用的递归函数的时间复杂度 [英] Time complexity of a recursive function with two calls

问题描述

考虑以下代码：

def count_7(lst):
    if len(lst) == 1:
        if lst[0] == 7:
            return 1
        else:
            return 0

    return count_7(lst[:len(lst)//2]) + count_7(lst[len(lst)//2:])

注意：切片操作将被视为O（1）。

note: the slicing operations will be considered as O(1).

因此，我的直言是告诉我它是O（n * logn），但是我正在努力地进行科学证明。

很高兴获得帮助！

So, my inutation is telling me it's O(n*logn), but I'm struggling proving it scientifically.
Be glad for help!

推荐答案

好的，从数学上讲（排序of;）我得到这样的东西：

Ok, mathematically (sort of ;) I get something like this:

T(n) = 2T(n/2) + c
T(1) = 1

推广方程式：

T(n) = 2^k * T(n/2^k) + (2^k - 1) * c
T(1) = 1

n / 2 ^ k == 1 当 k == logN 时：

T(n) = 2^logN * T(1) + (2^logN - 1) * c

因为 T（1）= 1 并应用对数性质

T(n) = n * 1 + (n-1) * c
T(n) = n + n * c
T(n) = n * (1+c)
T(n) = O(n)

这是不是 O（n * logn）是因为您不必合并两个子问题。与 mergesort 不同，在这里必须合并两个子数组，此算法不必对递归结果做任何事情，因此其时间可以表示为常量 c 。

A clue that this is not O(n*logn) is that you don't have to combine the two subproblems. Unlike mergesort, where you have to combine the two sub arrays, this algorithm doesn't have to do anything with the recursive result, so its time can be expressed as constant c.

更新：直观

此算法应为O（n），因为您只能访问数组中的每个元素一次。这似乎并不简单，因为递归从来都不是。

This algorithm should be O(n) because you visit each element in the array only once. It may not seem trivial because recursion never is.

例如，您将问题分为两个子问题，每个子问题的大小是一半，然后将每个子问题也分为一半的大小，并且将继续进行下去，直到每个子问题的大小都1. 完成后，您将拥有n个大小为1的子问题，即 n * O（1）= O（n）。

For example, you divide the problem in two subproblems half the size, each subproblems is then divided in half the size too and will keep going on until each subproblem is of size 1. When you finish, you'll have n subproblems of size 1, which is n*O(1) = O(n).

从第一个问题的开始到N个大小为1的问题的路径是对数的，因为在每一步中，您都分为两步。但是在每个步骤中，您对结果什么都不做，因此不会增加解决方案的时间复杂性。

The path from the beginning of first problem until N problems of size 1 is logarithmic, because in each step you subdivide in two. But in each step you do nothing with the result so this doesn't add any time complexity to the solution.

希望这会有所帮助

这篇关于具有两个调用的递归函数的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！