计算字符串递归方法中的辅音

Question

这是python中写的方法：

def count_con(s, lo, hi):
    vls = ['a', 'e', 'i', 'o', 'u']
    if lo == hi:
        if s[lo] not in vls:
            return 1
        else:
            return 0

    mid = (lo + hi) // 2

    count_l = count_con(s, lo, mid)
    count_r = count_con(s, mid + 1, hi)

    return count_l + count_r

假设我们想求出它的时间复杂度。我想出了一个递归关系：

T(n) = 2T(n/2) + f(n), if n > 1 or T(n) = O(1), if n <= 1

但是，我无法确定 f(n) 会是什么。合并这两部分是否需要线性 O(n) 时间，就像合并排序或常数 O(1) 时间一样？我倾向于认为，因为它只是一个加法常数O(1)时间更合适。

总的来说，这个方法是O(n*logn)还是O(logn)？

Answer 1

Will combining the two halves take linear O(n) time just like in merge-sort or constant O(1) time? I tend to think that since it's only an addition constant O(1) time is more suitable.

你是对的。

因此，如果我们假设一次调用完成 1 个工作单元（忽略递归调用），我们所要做的就是确定调用次数。如果我们假设 n = 2^k 我们最终会调用 1 + 2 + 4 + ... + 2^k = 2n - 1 次调用。这只是 O(n)。

Answer 2

如您的问题所述，合并两半仅消耗常数时间。代码所做的是，简单地递归检查（访问）索引是否为元音并递增计数器。它的整体只有 O(n).

如果您需要了解何时出现对数复杂度，可以查看此问题以了解一般的时间复杂度：here

f(n) 如您的问题中所述，这里只需要常数时间，但在合并排序中，这是一个 O(n)，因为在递归调用之后，在返回排序数组之前，您正在访问并线性排列左右索引之间的整个数组的值。

计算字符串递归方法中的辅音

Count consonants in string recursive method

python

recursion

time-complexity