情報 大学生・専門学校生・社会人 1年以上前

線形探索と二分探索の問題です。 解説も踏まえて、教えてくれると嬉しいです。

問7. 整列済み (大きさの順に並んでいる) データ列から、目的の数値が何番目にあるのか、 もしくは、目的の数値はデー タ列にはないのかを求めたい. 線形探索 (先頭から順に比較して探す)を行う場合と、二分探索 (対象範囲のちょうど真ん 中のデータを比較してその結果により対象範囲をせばめていく)を行う場合について, 設問に答えなさい。 ( 10点) (1) 計算量のオーダーをそれぞれ答えなさい。 「線形探索: (2) 1000 個のデータ列に対して線形探索と二分探索を行うとき、 最悪の場合で何回の数値の比較を行うことになるか をそれぞれ答えなさい. 二分探索:

情報 大学生・専門学校生・社会人 3年弱前

アルゴリズムと時間計算量を教えて欲しいです

アルゴリズムとデータ構造 問1n個のデータのうちk番目に大きい値を返すアルゴリズムを示しなさい。 また、そのアルゴリ ズムの時間計算量を評価しなさい。 アルゴリズムは、 そのステップが分かる程度の詳細さで記述す ること。記述は、疑似言語、 自然言語 (日本語または英語)を用いること。

情報 大学生・専門学校生・社会人 約3年前

【計算量】 表の求め方分かりますか？ また、2^nについては、小数点をどうするのかが分かりません。

問題2.4.4 ★★ 次の表は「Nがどの程度の大きさであればおおよそ何回の計算を行うか」 を表したものです。 この表 を完成させてください。 なお、 計算回数の定数倍 (例:10№2 の "10" の部分)は考えないものとします。 また、 logの底は2であるものとします。 計算回数 実行時間目安 N log N N2 2N 10°回以内 0.001 秒以下 N≤ 60,000 N ≦ 1,000 N≤ 20 107 回以内 0.01秒以下 10°回以内 0.1秒以下 10°回以内 1秒以下