1

私がこの入力を持っていると仮定しましょう：リストのリスト

（def list-of-list-3 （list（list 1 2 3）（list 4 5 6）（list 7 8 9）））

（map＃（reduce *％1）list-of-list3）

この場合、map-reduceの複雑さはO（n ^ 2）ですか？

map-reduceは2つのネストされたものとして変換されますか？

したがって、上記の例をclojure REPLで実行すると、複雑さの時間はO（n）のように見えます。

入力サイズを複製する場合（list-of-list-6（list（list 1 2 3）（list 4 5 6）（list 7 8 9）（list 8 2 3）（list 9 8 1）（list 7 6 4）））時間は二次式ではなく、直線的に増加します。

誰もが理由を言うことができますか？

前もって感謝します

4

2 に答える 2

4

これはO（n ^ 2）ではなく、おおよそO（n * m）です。ここで、nはリストの数、mはリストの長さです。さまざまな数の長さに関係する他の要因もあります。手でそれを行い、理由を確認するために自分で時間を計ってください！

于 2010-12-28T12:05:30.693 に答える
2

この場合、map-reduceにはO(n^2)複雑さがありますか？

n式の中で何に対応するかを教えてくれない限り、言うことはできませんlist-of-list-3。

ちなみに、O(n^2)またははO(n*n)二次の複雑さであり、指数関数的な複雑さではありません。指数関数的な複雑さO(e^n)。

入力サイズを[2倍]にすると

( list-of-list-6 (list (list 1 2 3) (list 4 5 6) ( list 7 8 9) 
                       (list 8 2 3) (list 9 8 1) (list 7 6 4)) )

時間は指数関数的ではなく、直線的に増加します。

このnことから、は外側のリストの長さであると思われます。もしそうなら、reduce実際にはそうではO(n)ありませんO(n^2)。二次成長を得るには、次のように定義する必要がありますlist-of-list-6。

( list-of-list-6 (list (list 1 2 3 4 5 6) (list 4 5 6 1 3 2) 
                       (list 7 8 9 1 2 3) (list 8 2 3 2 3 4) 
                       (list 9 8 1 2 3 4) (list 7 6 4 5 6 7)) )
于 2010-12-28T12:10:16.903 に答える