2

それぞれ長さが n の 5 つのソートされたリスト: List1、List2、List3、List4、List5 が与えられます。5 つの (int) 数値 (各リストから 1 つ) がある場合、合計が 0 になると true を返します。私の目標は、アルゴリズムが O(n) であることを確認することです。頭のてっぺんから、5 つのリンクされたリストの合計を持つハッシュ マップを作成するか、[o(n*n*n*n*n)] のように 5 つのリストを評価することを考えることができます。複雑さを最適化または軽減する方法を探していますが、行き詰まっています。

Python での私のコード:

def getIndicesFromFiveArrays(List1,List2,List3,List4,List5,t):
    a,b,c,d,e=0,0,0,0,0
    while(List1[a]+List2[b]+List3[c]+List4[d]+List5[e]!=t):
        b=b+1
        if b==len(List2):
            return (-1,-1)
        if List1[a]+List2[b]+List3[c]+List4[d]+List5[e]<t:
            a=a+1
            b=b-1
        c=c-1
        d=d-1
        e=e-1
            if a==len(List1):
                return (-1,-1)
    return (a,b,c,d,e)

編集 1: ちなみに、これは宿題ではありません。他の質問を確認して、自分で確認してください。ありがとう..

4

2 に答える 2

2

MRAB のコメントに触発された O(n^3) ソリューションがあります。

まず、リスト 1 のすべての値をリスト 2 のすべての値と組み合わせて、セットに格納します。結果セット 1and2 を呼び出すと、n^2 の値が含まれます。

次に、セット 1and2 をリスト 3 と結合します。結果セット 1and2and3 を呼び出します。これには n^3 の値があり、構築には n^3 ステップが必要です。

次に、リスト 4 と 5 を結合します。結果セット 4and5 を呼び出します。n^2 の値があります。

最後に、セット 4and5 のいずれかの値がセット 1and2and3 の値の逆数に等しいかどうかを確認します。このステップには n^2 ステップかかります。

このアプローチでは、O(n^3) 空間と O(n^3) 時間を使用します。

Karoly Horvath が指摘しているように、実際にはセット 1and2and3 を保存する必要はなく、最後のステップでセット 1and2 からオンザフライで構築できます。このアプローチでは、O(n^2) スペースしか使用しませんが、O(n^3) 時間は必要です。コードは次のとおりです。

l1 = [1,2,3,4,5,10]
l2 = [1,2,3,4,5,11]
l3 = [1,2,3,4,5,12]
l4 = [1,2,3,4,5,13]
l5 = [1,2,3,4,5,-46]

def test():
    l1_2 = [a + b for a in l1 for b in l2]
    set4_5 = set([a + b for a in l4 for b in l5])
    return any([True for x in l1_2 for y in l3 if -(x + y) in set4_5])

print test()
于 2012-07-19T21:21:16.963 に答える
0

リストが 2 つある場合は、リスト 1 から数値を取得し、リスト 2 でその数値のマイナスを探します。リスト 2 をセットに置き換えた場合、全体の複雑さは O(n) になります。

3 つのリストがある場合、リスト 1 から番号を取得し、次にリスト 2 から番号を取得し、複雑さは O(n^2) になります。リスト 3 をセットに置き換えると、全体の複雑さは O(n^2) になります。

したがって、5 つのリスト/セットの全体的な複雑さを O(n^4) 未満に減らすことはできないと思います。

于 2012-07-19T14:57:14.927 に答える