Python-求一道codility算法题的时间复杂度

Python-求一道codility算法题的时间复杂度

夜无邪 发布于 2016-11-22 字数 2975 浏览 1251 回复 1

这是一道codility.com的题目,英文题目如下:

A non-empty zero-indexed array A containing N different integers is given. We are looking for the longest possible sequence built from elements of A, A[B[0]], A[B[1]], ..., A[B[K]], satisfying the following conditions:
The sequence must be decreasing; that is, A[B[0]] > A[B[1]] > ... > A[B[K]].
For any two consecutive elements of the sequence, A[B[I]] and A[B[I+1]], all the elements of A between them must be smaller than them; that is, for any J = MIN(B[I], B[I+1]) + 1, ..., MAX(B[I], B[I+1]) ? 1, we have A[J] < A[B[I+1]].
Write a function:
def sequence(A)
that, given a zero-indexed array A containing N different integers, computes the maximum length of a sequence satisfying the above conditions.
For example, for the following array A:
A[0] = 9 A[1] = 10 A[2] = 2
A[3] = -1 A[4] = 3 A[5] = -5
A[6] = 0 A[7] = -3 A[8] = 1
A[9] = 12 A[10] = 5 A[11] = 8
A[12] = -2 A[13] = 6 A[14] = 4
the function should return 6.
A sequence of length 6 satisfying the given conditions can be as follows:
A[9] = 12 A[1] = 10 A[4] = 3
A[8] = 1 A[6] = 0 A[7] = -3
Assume that:
the elements of A are all distinct;
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [?1,000,000,000..1,000,000,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

我用python写了一个递归去得到这个结果,但是我不太会估计我的算法的时间复杂度(因为有递归调用),所以希望大侠们能够帮我评估下我的代码的时间复杂度,或者能够给出题目要求的O(n)的解法。以下是我的代码:

def getMaxIndex(arr, min, max):
mid = min
maxValue = arr[min]
for index in range(min,max+1):
if arr[index] > maxValue:
mid = index
maxValue = arr[mid]
print str(index) + "****" + str(mid) +"-----" + str(max) + "====" + str(maxValue)
print "----" + str(mid)
return mid

def maxL(arr, min, max):

if min == max:
return 1
if (max - min) == 1:
return 2

mid = getMaxIndex(arr, min, max)
if mid == max:
return maxL(arr, min, mid-1)+1
if mid == min:
return maxL(arr, mid+1, max)+1
tmpA = maxL(arr, min, mid-1)
tmpB = maxL(arr, mid+1, max)
print "++++" + str(tmpA) + "+++" + str(tmpB)
if tmpA > tmpB:
return tmpA+1
else:
return tmpB+1

testArr = [9, 10, 2, -1, 3, -5, 0, -3, 1, 12, 5, 8, -2, 6, 4]
print maxL(testArr, 0, len(testArr)-1)

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

灵芸 2017-03-14 1 楼

其实你的思路是完全正确的。只是你的算法中间,每次找最大值都要把整个数组遍历一遍,而实际上最大值问题是有递归子问题性质的。要考虑怎么在分解
正如你算法的思路那样:对于任意一个B[m]来说,B[m+1]...B[K]要么都小于B[m],要么都大于B[m]。(性质(1))
方便起见,对任意的i,如果B[i] < B[i+1],称为数列在i处“向右”;否则称为数列在i处“向左”。
考虑任意一个满足条件的B[K],一定存在某个m,使得:m = K,或者B[m] > B[m+1](也就是说,B[k]从第m项开始向左拐了)。记所有这样的m中间最小的为M,那么一定有:
B[i] < B[i+1], 对任意i < M
M = K,或者B[M] > B[M+1]
也就是说,B[K]可以分解成两个阶段:连续向右的阶段;和一次向左以及之后的阶段。

对于所有的n,0 <= n < N,定义满足条件:B[0] = n的题目中描述的B[k]序列的长度(即K+1)最大的序列为“n起始最大子递减序列”,记为F[n];
进一步,如果B[0] = n,且K=0或者B[1] > n,满足该条件的所有B[k]序列长度的最大值为“n起始最大向右递减序列”,记为F1[n];相似的,如果K=0或者B[1] < n,满足条件的所有B[k]序列长度最大的序列为“n起始最大向左递减序列”,记为F2[n]。
显然有F[n] = max(F1[n], F2[n])

对所有的n,0 <= n < N,定义满足条件:B[K] = n,且对所有0 <= i < K,有B[i] < B[i+1](即连续向右)的题目中描述的B[K]序列的长度(即K+1)最大的序列为“n终结最大连续向右递减序列”,记为G[n]。
显然对于任意的n,如果B[K] = n,则B[K-1]是唯一确定的。进一步地不难发现,G[n]是由G[n-1]中大于A[n]的部分,再加上A[n]组成。

因此有所求答案 = max_n{ |G[n]| + |F2[n]| - 1},其中|G[n]| |F2[n]|表示序列长度
而同时,如果B[I] = n,B[I+1] < n,则B[I+1]可以取的位置只有有限多个,恰好是G[n-1]中,小于A[n]的部分。

综上所述,大致的算法是这样的:

从左到右处理整个数组。用一个堆栈维护当前的G[n],并对G[n]中每一项存储F[G[i]]的值。
说不明白的话看代码也许更清楚一点:

int stack[MAX_N][2]; //满足空间O(n)的条件
int stackptr = 0;

int maxL = 0; //最终结果

for(int i = 0; i < N; i++)
{
int F2, F = 0;
//F 记录F[G[m]],即堆栈中的数的最大递减序列长度。由向左递减和向右递减中的最大值得到;而向右递减是利用G自身的性质计算。
//F2 记录F2[i],即i起始最大向左递减序列长度;它由F求得。
while(stackptr > 0 && stack[stackptr-1][0] < A[n])
{
if(F + 1 > stack[stackptr-1][1])
{
F = F + 1;
}
else
{
F = stack[stackptr-1][1];
}
//出栈
stackptr--;
}
//因为F是递增的,所以只要用F的最终值即可。
F2 = F + 1;
if(F2 + stackptr > maxL)
{
maxL = F2 + stackptr;
}
//进栈
stack[stackptr][0] = A[n];
stack[stackptr][1] = F2;
stackptr++;
}

因为每个数进栈一次、出栈一次,所以总的时间复杂度是O(n)。