- ベストアンサー
Dijkstra法のデータ構造による計算量の変化
Dijkstra法を実行するプログラムを隣接行列と隣接リストを用いてそれぞれ実装しました。 そこでデータ構造の違いによる計算量の違いをオーダー表記を用いて表そうとしているのですが どのように計算すればいいのか検討がつきません。 次の点に行くためにどのような処理が必要か、また点を訪れてからどのような処理が必要かを求めれば良いみたいです。 回答よろしくお願いします。
- saldsstripe
- お礼率0% (0/3)
- C・C++・C#
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
単純には, 各処理に対して 「1回あたりの所要時間」と「実行回数」の積 を積算するだけ.
関連するQ&A
- Dijkstra法
大学２年生です。 教えてください。 有向ネットワークN=(V,E,d)におけるDijkstra法に関して以下の問いに答えなさい。 1、Dijkstra法は、（Nの他に）『何を指定されて何を計算する』アルゴリズムか。 2、Dijkstra法が正しく働くために。枝の長さd=(dij)はどのような条件を満たさなければならないか。 3、Dijkstra法は、アルゴリズムの実行過程で、Vの各点に数値（ラベル値）をつけ、それを更新して行く。実行の各段階におけるラベル値の性質によって、Vは2つの集合S１、S２に分割される。どのような性質によって分割されるのか述べなさい。 ４、実行の各段階で、S２の要素１個が、S１に移される。どのような要素がS２からS１へ移されるのか。 ５、４の操作が有効であるように、S２に属する点のラベル値はある性質（S１に属する点のラベル値達との間のしかるべき関係）を満たすよう保たれる。その関係式を示しなさい。
- 締切済み
- 情報工学
- データ構造とアルゴリズムの問題が分かりません。
以下の問題で悩んでいます。 １ 配列とリストでデータを末尾に追加する場合の時間計算量をO記法で表せ。 ２ 配列とリスト、それぞれの時間計算量以外の利点と欠点をなるべく多く挙げよ。 ３ データ構造「スタック」、「キュー」を配列もしくはリストで実現した場合、それぞれの利点と欠点を挙げよ。 ４ アルゴリズム「線形探索」、「二分探索」で特定のデータを検索するための時間計算量をO記法で表し、またその理由も記述せよ。 ５ データを検索する操作のほうが多い場合と、データを追加する操作が多い場 合、 「線形探索」と「二分探索」どちらが有利か理由をつけて述べよ。 １は、挿入と削除はO記法で表せたのですが、追加が分かりませんでした。 ２は配列の利点はランダムアクセス可能な点と任意のデータをすぐに扱える点の２点 リストの利点は扱うデータを自由に変えられる点の１点しか思いつかず、欠点はよく分かりませんでした。 ３、４、５も理由をつけて説明しろと言われたら無理です。 テストに類題を出すと先生はおっしゃってたので、どうしてもすぐに回答が必要です。先生にも質問したのですが、テストに類題を出すから教えられない。自力で頑張れと言われ困っています。 どなたか御助力よろしくお願いいたします。
- ベストアンサー
- C・C++・C#
- Javaを使った行列計算
Javaを使って行列の固有値などを求めるプログラムを 作りたいと考えています。そこで、自分で全て実装する前に Javaのライブラリの中に行列を扱うクラスなどがあるのならば それを利用したいと考えています。そこで、Javaのライブラリに 行列計算に適したクラスなどは用意されているでしょうか。 もしありましたら、教えて頂きたいと思います。お願いします。
- ベストアンサー
- Java
- 計算量オーダーについて O(1/n)オーダー？
こんにちは、c#初心者です。 今回は計算量オーダーの話なので、基本的に言語は関係ないと思います。 計算量オーダーの基本的な部分は分かるのですが、O(1/n)オーダーのアルゴリズムは（今のところは）まだ見かけないというか、名前程度しか知らないので、これに関しては無知です。そこで、この場合はどういうオーダーになっているのかという質問です。 質問は３つあります。 １）この一連の処理はO(1/n)オーダーになっているか？ int count = 1000 / length; // lengthは正の整数 for ( int i = 0; i < count; i++ ) Do(); // O(1)オーダーの処理 ２） （１がO(1/n)の場合）繰り返す処理がO(n^2)になった場合に、この一連の処理はO(n)オーダーになるのか？ int count = 1000 / length; // lengthは正の整数 for ( int i = 0; i < count; i++ ) Do(); // O(n^2)オーダーの処理 ３）配列型のコレクション（コレクションって、c#の呼び方だったっけ？） [c#] List<T>,[c++] Bector, [Java] ArrayList(だったっけ？)のようなクラスのAddメソッドのオーダーは？ //Addメソッドの中身 if ( Capacity == Count ) Expand(); // Expandは配列の容量を２倍に拡張するO(n)処理とします。 array[Count++] = item; 以上です。 補足で、２）については大学の教授に「一回でもO(n^2)の処理が呼び出されたら、O(n^2)オーダーになる」と言われましたが、納得いかないです。確かに、O(1/n)オーダーの処理の後にO(n^2)オーダーの処理を行えば、そうなるのは納得いくのですが……という感じです。教授が読み間違えたとは考えにくいですが（確かにちょっと忙しそうでしたが）、念のため質問です。 それと、３）はよくある配列型のコレクションのまねです。「もし内容物が容量一杯になれば拡張→追加」を繰り返すとした場合です。ExpandメソッドのオーダーがO(n)なので、単純に計算すればO(n)オーダーになるのですが、呼び出される頻度が「(拡張された容量)回に１回」です。 例えば、容量が４ずつ拡張されるとすれば、「４回に１回」拡張が必要になり、１０ずつ拡張されるとすれば、「１０回に１回」の拡張が必要です。この場合、どう考えても全体として定数で割っているだけなので、O(n)オーダーのままになるのは明白なのですが、今回は容量２倍とさせていただきました。すると拡張の頻度は「（さっきまでの容量）回に１回」の頻度で、容量に反比例し、直感的にはO(Count / Capacity) = O(1)オーダーに見えるのですが、この判断は正しいでしょうか？ 皆さんのご意見を伺わせてください。
- ベストアンサー
- C・C++・C#
- データ構造とアルゴリズムの違いについて教えて頂けないでしょうか。
データ構造とアルゴリズムの違いについて教えて頂けないでしょうか。 データ構造とアルゴリズムについて学習しています。 （質問事項） ・データ構造とアルゴリズムの違いについて教えて頂けないでしょうか。 詳細に教えて頂けると大変助かります。 （私の現状） たとえば、データ構造は、単純なものでは、配列やコレクション、２分木などの構造で、アルゴリズムは２分木探索の実装方法だと思っています。 データ構造とアルゴリズムについては初心者です。 （現在、就職活動中で、これらを学ぶ必要がありご質問させて頂いています） どうか、皆様、教えて頂いた情報を最大限に活用させていただきますので、（皆様にとってはくだらない質問かもしれませんが…）どうぞよろしくお願いいたします。
- 締切済み
- その他([技術者向] コンピューター)
- 漸化的計算量のオーダー記法O表記について
漸化的計算量のオーダー記法O表記について オーダー記法Oでの表記の仕方って、ようするにnをn→∞とした時に、一番大きくなる項を抜き出しきて、n→∞の時、増加量が微少な係数は無視をする。という考え方でいいんでしょうか？ 例えば 1000*(2^n)+0.5(n^n)=O(n^n) nlogn+n√n=O(n√n) n^2.01+(n^2)log(n^2)=O((n^2)log(n^2)) であってますか？
- ベストアンサー
- その他([技術者向] コンピューター)
- プログラマにとって「アルゴリズム」や「データ構造」の知識は必須ですか？
最近の、いわゆるパッケージソフトウェアや、Webアプリケーションの開発においては、 必要なコンポーネントをインポートして部品を組み立てていくイメージで コードを書いていくというのが主流だと思います。 ほとんどのプログラミング言語には、すでに便利な関数やパッケージが用意されており、「アルゴリズム」や「データ構造」といった知識はあまり必要になりません。 例えば、データをソートしたい場合、クイックソートなどで自分で実装しなくても、すでにソート関数が用意されているので、その関数を使用すれば良いわけです。 そのような環境においても、プログラマにとって「アルゴリズム」や「データ構造」の知識はやはり必須ですか？ 時々、 ・「優先順位付き待ち行列」くらいは、スラスラ実装できなければ、プログラマとしては半人前 ・「離散数学」をしっかり理解していないと、プログラマとしては致命的 などという話も聞くのですが、皆さんの意見を聞かせてください。
- ベストアンサー
- Java
- CSVファイルを読み込んで計算するには、構造体か？
はじめまして。C++プログラミングの質問です。 初心者レベルの質問で申し訳ないのですが、お付き合いください。 CSVファイルを読み込んで、書かれている値を使ってある計算を行う、 ということをしたいのですが、処理方法をどうするか悩んでいます。 CSVファイルに書かれる最大行86400行、最大列6000列です。 また、開発環境はLinuxとなります。 私は「CSVファイルの項目を構造体に格納するクラス」と、「構造体の値を使って計算 するクラス」を考えました。 しかし、構造体ですと最大86400行のものを格納するのは、メモリを食うだけで無駄だという 指摘を受けました。 直接ファイルから値をとってきて、計算クラスに処理させるほうが無難と言われましたが、 「CSVファイルの項目を構造体に格納するクラス＝データベース」と考えており、 後々拡張する場合に融通が利くのではないでしょうか。 経験が浅いので、断固たる主張ができないのですが・・・ 構造体に入れることばかり考えていたので、開発のボリュームを抑え、かつ、メモリを食わない 方法を全く思いつきません。 有識者の方へアドバイスを受けたいのですが、 ・大量のデータを読み込む場合、構造体等に格納する方が後ほど助かるか、 それとも、直接ファイル読み込みした方がよいか ・構造体格納のほかに相応しいやり方はないか この2点をメインにお答えいただけないでしょうか。 何か良いやりかたがありましたら教えていただきたいです。 よろしくお願い致します。
- ベストアンサー
- C・C++・C#
