1

私は現在HaskellでCSクラスを受講していますが、いくつかの資料を理解する上で深刻な問題を抱えています。

私の割り当ての1つとして、2つのデータ型が与えられ、定数時間の追加を持つ追加関数を作成するように求められました。

私は与えられます：

data NNList a = Sing a | Append ( NNList a) ( NNList a) deriving (Eq)
data CList a = Nil | NotNil ( NNList a) deriving (Eq)

そして私は関数を書くように頼まれました：

CListAppend :: CList a -> CList a -> CList a

CS教育で何を逃したのかはわかりませんが、時間と空間の複雑さに戸惑うことがよくあります。関数が関数であるconstant timeかどうかを実際に知るにはどうすればよいでしょうか。そして、誰かがこの質問をどのように進めるかについてのアイデアを私に提供できますか？

私の試み：

CListAppend :: CList a -> CList a -> CList a
CListAppend Nil rl = rl
CListAppend ll Nil = ll
CListAppend ll rl = NotNil $ Append ll rl

これは、CListの代わりにNNListを返すエラーを報告します。それを変換する方法はありますか？

4

2 に答える 2

6

時間計算量は、入力のサイズに関連して回答を計算するために必要なステップ数を説明する方法です。ステップを構成するものとサイズの計算方法は、問題によって異なります。

たとえば、分類されていない名刺の山がある場合、特定の名刺を検索するには、カードの数に比例したステップ数が必要になります。パイルのサイズを2倍にすると、調べなければならないカードの平均数も2倍になります。

一方、カードを事前に並べ替えた場合は、「高低」ゲームをプレイして、カードを見るたびに山のサイズを半分に減らすことができます。パイルのサイズを2倍にすると、特定のカードを探すときに1ステップ追加するだけで済みます。

これらは、それぞれ線形および対数の時間計算量の例です。あなたの場合、一定の時間計算量が必要です。つまり、2つのリストがいくら大きくても、それらを追加するには同じステップ数が必要です。

通常、さまざまな入力を使用して紙のアルゴリズムをウォークスルーすることでアイデアを得ることができますが、より正確な方法があります。標準のリスト実装を使用した追加関数の例を次に示します。[]

append []     bs = bs
append (a:as) bs = a : append as bs

追加する再帰呼び出しを1つのステップとしてカウントします。あるいは、の呼び出しの数を数えることもできます(:)。最初の引数が空のリストで[]ある場合、再帰呼び出しはありません。リストに単一の要素が含まれている場合、、[1]を評価する1 : append [] bsため、再帰呼び出しが1つあります。次に、で入力サイズを2倍にし[1,2]、再帰呼び出しをカウントします。次に、などを使用して再度2倍にし[1,2,3,4]ます。次に、入力のサイズでステップ数が一定、線形、対数、指数などであるかどうかを概算できます。

于 2013-03-26T02:41:16.670 に答える
0

最後の定義は間違っています。でllある場合、あなたの定義は次のようになります。NotNil xrlNotNil y

CListAppend (NotNil x) (NotNil y) = NotNil ( Append x y )

ただし、タイプの値にAppendを適用していますCList a。

また、この解決策は一定時間です。Appendコンストラクターは処理を行いません。また、パターンマッチングは一定時間で行われます。

于 2013-03-27T02:04:32.370 に答える