質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

2回答

2643閲覧

再帰の計算量の算出方法について

退会済みユーザー

退会済みユーザー

総合スコア0

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2016/09/02 10:58

次のコードにおいて、計算量の算出ってどのように行うのでしょうか?
O(N)の計算時間なのですが、これがどのように算出したのかが分かりません。

二分探索木が与えられた時、同じ深さのノード同士の連結リストを作るアルゴリズムを設計してください。(例えば、深さDの木がある時、D個の連結リストを作ることになります。)

Java

1void createLevelLinkedList(TreeNode root, ArrayList<LinkedList<TreeNode>> lists, 2 int level) { 3 if(root == null) return; 4 5 LinkedList<TreeNode> list = null; 6 if(lists.size() == level) { //この深さがまだリストに含まれていない 7 list = new LinkedList<TreeNode>(); 8 /*深さは探索が進むに従って増加する。 9 従って、深さiの頂点に初めて到達した時、 10 深さ0〜i-1の頂点にのみ到達している。 11 なので、深さiのために新しいリストを作って追加すれば良い */ 12 13 lists.add(list); 14 } else { 15 list = lists.get(level); 16 } 17 list.add(root); 18 createLevelLinkedList(root.left, lists, level + 1); 19 createLevelLinkedList(root.right, lists, level + 1); 20 } 21 22 ArrayList<LinkedList<TreeNode>> createLevelLinkedList(TreeNode root) { 23 ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>(); 24 createLevelLinkedList(root, lists, 0); 25 return lists; 26 }

コード中に再帰があるので、漸化式を使ったりするみたいですが、この場合どのような漸化式になるのでしょうか?
お分かりの方、おたすけください。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

解決済みのようではありますが横槍を失礼します。「計算量」と単純に仰られても、これだけでは意味が漠然とします。そもそも定義が確定しません。

まず、計算量とは「時間」についてのものと、「メモリ空間」についての二通りがあります(本問では時間と指定されていますが)。また、計算の基準となる処理(固定時間、固定メモリで実現できることが確実であるもの)を明らかにしないといけません。この上で、「Nを何の数とするか」を考えなければなりません。

たとえば、本問の場合「元の木のノード数をN」とも読めますし、「元の木の深さをN」とも読めます。

投稿2016/09/02 13:00

HogeAnimalLover

総合スコア4830

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

「漸化式」なんてややこしいことを考える必要はありません。

まず、一度呼ばれた時に関数をどれだけ呼び出すか考えてみると、

  • root == nullの場合、何も呼ばない。
  • それ以外の場合、左の子、右の子について1度ずつ同じ関数を呼ぶ。

ということで、この関数は同じノードについて2回実行されることもありませんし(もちろん、木構造がおかしくなっていないのが前提です)、逆にルートから繋がっているノードについては、どこかで必ず関数の処理対象となることになります。同様に、端っこにあるnullについても、必ず関数が呼ばれます。

そして、ノードがN個ある場合、左右合わせて2N個のポインタがあります。このうちルート以外のN-1個は別なノードから指されていて、残りのN+1個はnullのままとなっています。

ということで、関数の実行回数は有効なノードN個+nullがN+1個の2N+1回となるので、O(n)となります。

投稿2016/09/02 11:19

maisumakun

総合スコア145121

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問