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

Question

以下の問題で悩んでいます。

１　配列とリストでデータを末尾に追加する場合の時間計算量をO記法で表せ。

２　配列とリスト、それぞれの時間計算量以外の利点と欠点をなるべく多く挙げよ。

３　データ構造「スタック」、「キュー」を配列もしくはリストで実現した場合、それぞれの利点と欠点を挙げよ。

４　アルゴリズム「線形探索」、「二分探索」で特定のデータを検索するための時間計算量をO記法で表し、またその理由も記述せよ。

５　データを検索する操作のほうが多い場合と、データを追加する操作が多い場　　　合、　「線形探索」と「二分探索」どちらが有利か理由をつけて述べよ。

１は、挿入と削除はO記法で表せたのですが、追加が分かりませんでした。

２は配列の利点はランダムアクセス可能な点と任意のデータをすぐに扱える点の２点　リストの利点は扱うデータを自由に変えられる点の１点しか思いつかず、欠点はよく分かりませんでした。

３、４、５も理由をつけて説明しろと言われたら無理です。

テストに類題を出すと先生はおっしゃってたので、どうしてもすぐに回答が必要です。先生にも質問したのですが、テストに類題を出すから教えられない。自力で頑張れと言われ困っています。　どなたか御助力よろしくお願いいたします。

HKB · Accepted Answer

１　配列とリストでデータを末尾に追加する場合の時間計算量をO記法で表せ。
配列 O(n)
リストO(1)

２　配列とリスト、それぞれの時間計算量以外の利点と欠点をなるべく多く挙げよ。
配列は一般にサイズ固定ですが、リストは一般にサイズ可変です。
実装方法にもよりますが、普通配列の方が構造・アルゴリズムが単純ですので、高速でメモリ消費量が少ないです。
リストでは、動的なメモリ管理(malloc/free)を使うことが多いので、
アルゴリズムがやや複雑で、速度・メモリ消費量の点では若干不利かもしれません。
逆にリストのほうが、多様なデータへの対応をしやすく、柔軟性が高いと言えるでしょう。


３　データ構造「スタック」、「キュー」を配列もしくはリストで実現した場合、それぞれの利点と欠点を挙げよ。
双方向リストを用いるのであれば、先頭に対する挿入・削除、末尾に対する挿入・削除は1stepで行えます。
キューの実現にリストを用いれば、キューへの追加・キューからの取り出しは簡単にできます。
キューの実現に配列を用いると、先頭要素を取り出す毎に、配列全要素のシフトが必要になるため、非効率です。

スタックは普通、末尾へのpush,popのみ許可するため、上の問題は生じず、配列でも問題はないと思います。
強いていうならば、配列はサイズ固定ですから、スタックに必要なサイズが見積もれない場合は不便でしょう。

４　アルゴリズム「線形探索」、「二分探索」で特定のデータを検索するための時間計算量をO記法で表し、またその理由も記述せよ。
※ 探索対象のサイズをNとします。
(線形探索) O(N) 前から順番に調べていくと、平均でN/2回で探索対象を発見できるため。
(二分探索) O(log N) 1回の探索毎に探索範囲を半分に絞り込むことができます。
そのため、探索対象のサイズが2倍になっても、探索回数は平均で1回のみ増加します。
よって、探索回数はlog_2 N(底2のlog)と見積もることができます。

５　データを検索する操作のほうが多い場合と、データを追加する操作が多い場合、　「線形探索」と「二分探索」どちらが有利か理由をつけて述べよ。
データ構造に双方向リストを用いるとします(末尾への追加はO(1))。
(検索が多い)二分探索　新しいデータはリストの順序（昇順・降順）が保たれるような位置に挿入します。
その位置は二分探索で見つけます。
こうしておけば、後でデータを検索する時に二分探索を用いることができますので、
挿入は低速ですが、検索は高速です。
(追加が多い)線形探索　新しいデータはとりあえずリスト最後尾に追加します。
検索が必要な場合はリスト先頭から順に探します。
双方向リストでは、リスト末尾への追加はO(1)ですので、データの追加は高速です。
一方、データはでたらめな順序で並んでしまうので、検索は線形探索で行うしかなく、低速です。

Tacosan · Answer

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

asuncion · Answer

> 自力で頑張れと言われ困っています。

でしたら、自力でできるところまでがんばりましょう。
教科書や参考図書に載っていませんか？

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

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

4 とか 5 は使うデータ構造がわからんので無視して 3 だけ:

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

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

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