みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

データ構造とアルゴリズムの問題が分かりません。

以下の問題で悩んでいます。

1 配列とリストでデータを末尾に追加する場合の時間計算量をO記法で表せ。

2 配列とリスト、それぞれの時間計算量以外の利点と欠点をなるべく多く挙げよ。

3 データ構造「スタック」、「キュー」を配列もしくはリストで実現した場合、それぞれの利点と欠点を挙げよ。

4 アルゴリズム「線形探索」、「二分探索」で特定のデータを検索するための時間計算量をO記法で表し、またその理由も記述せよ。

5 データを検索する操作のほうが多い場合と、データを追加する操作が多い場   合、 「線形探索」と「二分探索」どちらが有利か理由をつけて述べよ。

1は、挿入と削除はO記法で表せたのですが、追加が分かりませんでした。

2は配列の利点はランダムアクセス可能な点と任意のデータをすぐに扱える点の2点 リストの利点は扱うデータを自由に変えられる点の1点しか思いつかず、欠点はよく分かりませんでした。

3、4、5も理由をつけて説明しろと言われたら無理です。

テストに類題を出すと先生はおっしゃってたので、どうしてもすぐに回答が必要です。先生にも質問したのですが、テストに類題を出すから教えられない。自力で頑張れと言われ困っています。 どなたか御助力よろしくお願いいたします。

投稿日時 - 2008-01-22 19:12:45

QNo.3703821

すぐに回答ほしいです

質問者が選んだベストアンサー

1 配列とリストでデータを末尾に追加する場合の時間計算量をO記法で表せ。
配列 O(n)
リストO(1)

2 配列とリスト、それぞれの時間計算量以外の利点と欠点をなるべく多く挙げよ。
配列は一般にサイズ固定ですが、リストは一般にサイズ可変です。
実装方法にもよりますが、普通配列の方が構造・アルゴリズムが単純ですので、高速でメモリ消費量が少ないです。
リストでは、動的なメモリ管理(malloc/free)を使うことが多いので、
アルゴリズムがやや複雑で、速度・メモリ消費量の点では若干不利かもしれません。
逆にリストのほうが、多様なデータへの対応をしやすく、柔軟性が高いと言えるでしょう。


3 データ構造「スタック」、「キュー」を配列もしくはリストで実現した場合、それぞれの利点と欠点を挙げよ。
双方向リストを用いるのであれば、先頭に対する挿入・削除、末尾に対する挿入・削除は1stepで行えます。
キューの実現にリストを用いれば、キューへの追加・キューからの取り出しは簡単にできます。
キューの実現に配列を用いると、先頭要素を取り出す毎に、配列全要素のシフトが必要になるため、非効率です。

スタックは普通、末尾へのpush,popのみ許可するため、上の問題は生じず、配列でも問題はないと思います。
強いていうならば、配列はサイズ固定ですから、スタックに必要なサイズが見積もれない場合は不便でしょう。

4 アルゴリズム「線形探索」、「二分探索」で特定のデータを検索するための時間計算量をO記法で表し、またその理由も記述せよ。
※ 探索対象のサイズをNとします。
(線形探索) O(N) 前から順番に調べていくと、平均でN/2回で探索対象を発見できるため。
(二分探索) O(log N) 1回の探索毎に探索範囲を半分に絞り込むことができます。
そのため、探索対象のサイズが2倍になっても、探索回数は平均で1回のみ増加します。
よって、探索回数はlog_2 N(底2のlog)と見積もることができます。

5 データを検索する操作のほうが多い場合と、データを追加する操作が多い場合、 「線形探索」と「二分探索」どちらが有利か理由をつけて述べよ。
データ構造に双方向リストを用いるとします(末尾への追加はO(1))。
(検索が多い)二分探索 新しいデータはリストの順序(昇順・降順)が保たれるような位置に挿入します。
その位置は二分探索で見つけます。
こうしておけば、後でデータを検索する時に二分探索を用いることができますので、
挿入は低速ですが、検索は高速です。
(追加が多い)線形探索 新しいデータはとりあえずリスト最後尾に追加します。
検索が必要な場合はリスト先頭から順に探します。
双方向リストでは、リスト末尾への追加はO(1)ですので、データの追加は高速です。
一方、データはでたらめな順序で並んでしまうので、検索は線形探索で行うしかなく、低速です。

投稿日時 - 2008-01-23 08:42:14

お礼

丁寧な回答ありがとうございます。理解できました。

投稿日時 - 2008-01-23 18:35:07

このQ&Aは役に立ちましたか?

1人が「このQ&Aが役に立った」と投票しています

回答(3)

ANo.2

4 とか 5 は使うデータ構造がわからんので無視して 3 だけ:
キューやスタックで要求される操作を思い出して, それを配列やリストで「どのように実装するか」を想像すればわかりやすいかな. キューの方は自明でしょう. スタックはちと微妙. いずれにしても, 1 と関連するネタですな.

投稿日時 - 2008-01-22 21:30:33

お礼

回答ありがとうございます。 考えてみた結果、理解できました。

投稿日時 - 2008-01-23 18:36:38

ANo.1

> 自力で頑張れと言われ困っています。

でしたら、自力でできるところまでがんばりましょう。
教科書や参考図書に載っていませんか?

投稿日時 - 2008-01-22 21:22:23

お礼

レジュメや教科書を見て確認したのですが、質問に書いてあること以上はよく分かりませんでした。 よろしくお願いします。

投稿日時 - 2008-01-22 21:27:10

あなたにオススメの質問