C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[14]: 再帰をループに変換 [1]


(過去ログ 50 を表示中)

[トピック内 24 記事 (21 - 24 表示)]  << 0 | 1 >>

■27740 / inTopicNo.21)  Re[11]: 再帰をループに変換
  
□投稿者/ επιστημη (1380回)-(2008/11/13(Thu) 10:13:36)
επιστημη さんの Web サイト
No27727 (れい さん) に返信
> ■No27724 (dogatana さん) に返信
>>>>計算量はO(log n)が最大なので、最初にmalloc一発でいけますね。
> >>
> >>メジアンを必ず取れればそうなりますが、そうは問屋がおろさないのが難しいところです
>
> クイックソートの計算量はn^2が最大です。

空間計算量は要はスタック消費量なんだから最悪O(n)
時間計算量は最悪O(n^2)

じゃありませんっけ?
お二人が言及する"計算量"に食い違いがあるよな...

引用返信 編集キー/
■27757 / inTopicNo.22)  Re[12]: 再帰をループに変換
□投稿者/ dogatana (6回)-(2008/11/13(Thu) 21:04:10)
No27740 (επιστημη さん) に返信
> ■No27727 (れい さん) に返信
>>■No27724 (dogatana さん) に返信
> >>>>計算量はO(log n)が最大なので、最初にmalloc一発でいけますね。
>>>>
>>>>メジアンを必ず取れればそうなりますが、そうは問屋がおろさないのが難しいところです
>>
>>クイックソートの計算量はn^2が最大です。
>
> 空間計算量は要はスタック消費量なんだから最悪O(n)
> 時間計算量は最悪O(n^2)
>
> じゃありませんっけ?
> お二人が言及する"計算量"に食い違いがあるよな...

空間計算量と時間計算量というのは、わかりやすいですね。
もともと最大O(long n)のところに反応してしまったのでした。

それと、スタックの最悪消費量はO(n)であるものの実際に割り当てるとしたらどうなのよ?
と思ってたのですが、出水さんがかかれているとおり、log2(n)なのですね。

ソート済み配列をソートするのが一番スタック消費量が多いと考えたのですが、この場合、ピボットで分ける
とき片方が要素1のときにスタックを積まないようにすると、積むのはもう片方。これも次のループでpop
されるので、結局スタックのサイズは1で済む。

2つの部分配列に分割するときは1回あたり2個積まれるが、次のループで1個はpopされるので、結果として
消費量はlog2(n)で済む。

と、こんな理解をしたのですが、正しいでしょうか?

引用返信 編集キー/
■27759 / inTopicNo.23)  Re[13]: 再帰をループに変換
□投稿者/ 出水 (96回)-(2008/11/13(Thu) 23:08:23)
> ソート済み配列をソートするのが一番スタック消費量が多いと考えたのですが、この場合、ピボットで分ける
> とき片方が要素1のときにスタックを積まないようにすると、積むのはもう片方。これも次のループでpop
> されるので、結局スタックのサイズは1で済む。
>
> 2つの部分配列に分割するときは1回あたり2個積まれるが、次のループで1個はpopされるので、結果として
> 消費量はlog2(n)で済む。
>
> と、こんな理解をしたのですが、正しいでしょうか?

違います
詳しくはBlog書いたんでそちらを見てください
http://blogs.wankuma.com/izmktr/archive/2008/11/13/161309.aspx
引用返信 編集キー/
■27760 / inTopicNo.24)  Re[14]: 再帰をループに変換
□投稿者/ C学習中 (6回)-(2008/11/13(Thu) 23:22:47)
回答者の皆さま。
色々と興味深い回答ありがとうございます。

例えば

X のn乗
n!

の計算なら普通はループで組むでしょう。
再帰で組む人は少ないと思います。
私もどちらでも組めます。

しかしクイックソートはループでの組み方が
全く見当がつきませんでした。
しかし関数としてライブラリー化
されているようなものが、スタックオーバーの
危険を含む再帰で組まれている筈がないと考え
今回の質問をさせて頂きました。

επιστημηさんが纏められているように
スタックの確保領域をヒープに置くことが大事ですね。

R・田中一郎さんの回答もスタックなコレクションを
ヒープに置くとのことですが、私はスタックという言葉に惑わされて
勘違いしスタックに置くと考えた為暫く????状態でした。
(今はきちんと理解しています。)

あんどちん さんにエスパー能力を発揮して頂き
.SHO さんから質問にほぼ近い内容のコードを
書いていただきました。
私が欲しかったのはまさにこれです。これで
再帰からループに変換する考え方(コツ?)をつかみ
これを参考にしてJittaさんのコードを理解する所存です。

出水さん、dogatanaさん、れいさん、興味あるお話
ありがとうございます。

計算量の話が続いているので、聞きたい気がしますが
私が解決ずみにしないといけないきまりみたいなので
一応解決済みとします。

みなさん 有難うございました。




解決済み
引用返信 編集キー/

<前の20件
トピック内ページ移動 / << 0 | 1 >>

このトピックに書きこむ

過去ログには書き込み不可

管理者用

- Child Tree -