filter
有n
递归调用,但你也对每次迭代进行复制操作n
,所以你最终得到 Θ(n^2)。如果你“正确地”实现它,它应该是 Θ(n)。
对my_reverse
.
对revfilter_beta
.
revfilter_alpha
只做 afilter
然后 a reverse
,所以 Θ(n^2 + n^2) = Θ(n^2)。
编辑:让我们filter
再看看。
您要弄清楚的是相对于输入的大小执行了多少操作。O(n)
意味着在最坏的情况下,您将按照操作顺序进行n
操作。我说“按顺序”是因为您可以进行O(n/2)
操作,或者O(4n)
,但最重要的因素是n
. 也就是说,随着n
增长,常数因素变得越来越不重要,所以我们只看非常数因素(n
在这种情况下)。
filter
那么,对 size 的列表执行多少操作n
?
让我们从下往上看。如果n
是 0 - 一个空列表怎么办?然后它只会返回一个空列表。因此,假设这是 1 次操作。
如果n
是 1 呢?它将检查是否lst[0]
应该包括在内——不管调用需要多长时间f
——然后它会复制列表的其余部分,并对该副本进行递归调用,在这种情况下是一个空列表。所以filter(1)
需要f + copy(0) + filter(0)
操作,其中copy(n)
是复制列表需要f
多长时间,以及检查是否应包含元素需要多长时间,假设每个元素花费相同的时间。
怎么样filter(2)
?它将进行 1 次检查,然后复制列表的其余部分并调用filter
其余部分:f + copy(1) + filter(1)
。
你已经可以看到模式了。filter(n)
需要1 + copy(n-1) + filter(n-1)
.
现在,copy(n)
只是n
- 它需要n
操作以这种方式对列表进行切片。所以我们可以进一步简化:filter(n) = f + n-1 + filter(n-1)
.
现在您可以尝试扩展filter(n-1)
几次,看看会发生什么:
filter(n) = f + n-1 + filter(n-1)
= 1 + n-1 + (f + n-2 + filter(n-2))
= f + n-1 + f + n-2 + filter(n-2)
= 2f + 2n-3 + filter(n-2)
= 2f + 2n-3 + (f + n-3 + filter(n-3))
= 3f + 3n-6 + filter(n-3)
= 3f + 3n-6 + (f + n-4 + filter(n-4))
= 4f + 4n-10 + filter(n-4)
= 5f + 5n-15 + filter(n-5)
...
我们可以概括x
重复吗?那个1, 3, 6, 10, 15
... 序列是三角形数字 - 即 , , 1
,等。从到的所有数字的总和是。1+2
1+2+3
1+2+3+4
1
x
x*(x-1)/2
= x*f + x*n - x*(x-1)/2 + filter(n-x)
现在,什么是x
?我们会有多少次重复?好吧,您可以看到当x
=时n
,您不再有递归 - filter(n-n)
= filter(0)
= 1
。所以我们的公式现在是:
filter(n) = n*f + n*n - n*(n-1)/2 + 1
我们可以进一步简化:
filter(n) = n*f + n^2 - (n^2 - n)/2 + 1
= n*f + n^2 - n^2/2 + n/2 + 1
= n^2 - n^2/2 + f*n + n/2 + 1
= (1/2)n^2 + (f + 1/2)n + 1
所以你有它 - 一个相当详细的分析。那将是Θ((1/2)n^2 + (f + 1/2)n + 1)
......假设f
是微不足道的(比如f
= 1)Θ((1/2)n^2 + (3/2)n + 1)
。
现在您会注意到,如果copy(n)
花费了恒定的时间而不是线性的时间(如果copy(n)
是 1 而不是n
),那么您将不会n^2
在那里得到该术语。
我承认,当我Θ(n^2)
最初说的时候,我并没有在脑海中做这一切。相反,我想:好的,你有n
递归步骤,每个步骤都会花费n
大量时间,因为copy
. n*n = n^2
,因此Θ(n^2)
。为了更准确地做到这一点n
,每一步都会缩小,所以你真的有n + (n-1) + (n-2) + (n-3) + ... + 1
,最终与上面的数字相同:n*n - (1 + 2 + 3 + ... + n)
= n*n - n*(n-1)/2
= (1/2)n^2 + (1/2)n
,如果我在上面使用0
而不是 ,也是一样的f
。同样,如果您有n
步骤但每个步骤都采取了1
而不是n
(如果您不必复制列表),那么您将拥有1 + 1 + 1 + ... + 1
、n
times 或简单n
的 .
但是,这需要更多的直觉,所以我想我也会向你展示你可以应用于任何事情的蛮力方法。