O(n^2+nlogn)
O(n√n+nlogn)
O(nlogn+n^2)+O((n^1.67)logn)
O(nlogn+n^100)O(n^0.7+logn)

この4つの式をそれぞれ簡略化せよという問題なのですが、
考え方がよくわかりません。
どなたかご教授よろしくお願いします。

A 回答 (1件)

http://ja.wikipedia.org/wiki/ランダウの記号 の「4 一般的なオーダー」
http://ja.wikipedia.org/wiki/対数 の「2.3 特殊な底」

を参照すると,計算量の世界では lognという表記は慣例的に底=2が省略されているとみなしてもよいのですね。

オーダの考え方については,下記URLの該当箇所を参照。
http://ja.wikipedia.org/wiki/ランダウの記号 の「1.1 無限大における漸近挙動」

私の数学力は logとは何かを知っている程度で抽象的に式を展開できないので,nに比較的大きな値を代入してみて,この項の方が大きく変化するだろうとイメージしてみただけです。数学に詳しい方がいらっしゃいましたら,間違いをぜひ指摘していただきたいです。私にとってもたいへん勉強になります。

(1) O(n^2+nlogn)
例としてn=100としてみる。
左項は 100×100
右項は 100×log2(100)≒100×log2(128)=100×7
左項の影響が大きいので右項は無視できる。
【答】O(n^2)

(2) O(n√n+nlogn)
例としてn=100としてみる。
左項は 100√100 = 100×10
右項は 100×log2(100)≒100×log2(128)=100×7
左項の影響が大きいので右項は無視できる。
【答】O(n√n)

(3) O(nlogn+n^2)+O((n^1.67)logn)
例としてn=100としてみる。
左のオーダ式は(1)より O(n^2),よって100×100=10,000
右のオーダ式は(100^1.67)×log2(100)≒2188×log2(128)≒15,314
右のオーダ式の影響が大きいので左のオーダ式は無視できる。
【答】O((n^1.67)×logn)

(4) O(nlogn+n^100)O(n^0.7+logn)
左のオーダ式は(1)より O(n^100)
例としてn=100としてみる。
右のオーダ式の左項は 100^0.7≒25
右のオーダ式の右項は log2(100)≒log2(128)=7
左項の影響が大きいので右のオーダ式は O(n^0.7)
全体では O(n^100)×O(n^0.7) なので
【答】O(n^100.7)
    • good
    • 0
この回答へのお礼

詳しい説明ありがとうございました!

お礼日時:2008/05/07 19:05

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q一夜漬けタイプからコツコツタイプに変えたい

僕は今高校1年生の男です。
最近になって将来大学に行きたいと考え始めました。
もちろん行くためには一生懸命勉強しなければなりません。しかし、僕の場合は今まで中学時代の試験は全て一夜漬けで乗り越えてきました。一ヶ月程前にあった資格の試験も一夜漬けでなんとか合格出来たという感じです。没頭し始めると時間を忘れて物事に取り組めますが毎日コツコツとノルマを乗り越えて行くことが出来ません。どのようにして変えて行けばいいでしょうか。
もしかして、生まれつきのようなもので変えられないのですか。アドバイス宜しくお願いします。

Aベストアンサー

No.1です。 補足回答します。

ご質問1) 何に書いているんでしょうか。ノートですか。

回答) おすすめはパソコンのエクセルで表を作ることです。列や行を簡単に追加できるので、気楽に作り始めても、表が出来上がっていきます。表を作成後、運用していく時に、日々パソコンを立ち上げるのが面倒であるならば、表が出来上がったらそれを紙に印刷しましょう。(一つのセルを大きめにとった方が、手書きで追記しやすいです)。ある程度 紙で使ったら、定期的に(1回/週ぐらい)エクセルに入力すればいいです。

ご質問2) 時間も書いたほうが良いんでしょうか。例えば7時から数学の何ページから何ページまでという風に。

回答) 細かい時間は書かない方がいいです。あまり自分を縛り過ぎないように。細かい時間の計画通りには実行できないでしょう。午前・午後ぐらいで1日を分けた方がいいです。

Q一夜漬けの勉強方法について&コツコツタイプの方に質問です

私は今高1で、入学してから定期テストが3回ありました。明日からまたあるので4回目になります。私は最初はクラスで一夜漬けで一番をとれていたのですが、テストをするたびにコツコツタイプの子に抜かされて一つづつ順位が下がっていってしまってます・・・。 なのでこれ以上下がらないように今回のテストは早めにコツコツやろうと思っていたのですが、結局ずるずると勉強しないまま今日まで引き伸ばしてしまいました・・・たぶんまた順位が下がります(汗)そこで複数質問です。

(1)なるべく一夜漬けで覚えれる暗記方法(現代社会や英単語など)
(2)眠気の覚まし方(すぐ眠気に負けてしまいます)
(3)コツコツ勉強していくにはまず、何を始めればいいか

お願いします。

Aベストアンサー

(1)なるべく一夜漬けで覚えれる暗記方法(現代社会や英単語など)

睡眠時間は確保しましょう。
記憶は睡眠中に定着しますし、何より本番の集中力が低下するのは大きなマイナスです。

取り組むポイントをしぼり、「狭く深く」という勉強を時間をあらかじめ決めてやりましょう。
準備が出遅れている時点で、満点はあきらめることです。
広く浅く勉強しても、テストに通用する水準にはどれも達しない危険があるのです。

教科書に立ち戻り、重要語句の意味を別紙に書き出し、色ペンで関係する事項を書き足して、ノート作成によって覚えるなど「非効率的な方法」を試しましょう。

意味のない丸暗記は、忘れるために時間を使うような行為です。
時間がかかっても、勉強内容の「関係」を理解することで覚えるというやり方をおすすめします。

(2)眠気の覚まし方(すぐ眠気に負けてしまいます)

5感をフルに使うことです。
教科書やノートの音読、資料の切り貼り、暗記メモの組み立て、暗記ダンスや替え歌、飲み物や食べ物と暗記内容をセットにする作業など、単調な勉強方法にならないように工夫しましょう。

(3)コツコツ勉強していくにはまず、何を始めればいいか

計画を立てましょう。
欲張らず「必ずできる」と自分で思える少なめの内容にすることです。
そして、計画表にシールを貼ったり、赤丸チェックを入れるなど、成果を形にすることも大切です。
「いつまでにこれだけやる」と家族や友達に宣言するのも効果的です。

そうして、だんだんとできる量を増やすことです。
いきなりたくさんでは長続きしません。

(1)なるべく一夜漬けで覚えれる暗記方法(現代社会や英単語など)

睡眠時間は確保しましょう。
記憶は睡眠中に定着しますし、何より本番の集中力が低下するのは大きなマイナスです。

取り組むポイントをしぼり、「狭く深く」という勉強を時間をあらかじめ決めてやりましょう。
準備が出遅れている時点で、満点はあきらめることです。
広く浅く勉強しても、テストに通用する水準にはどれも達しない危険があるのです。

教科書に立ち戻り、重要語句の意味を別紙に書き出し、色ペンで関係する事項を書き足...続きを読む

QNHK もの知り一夜漬けのテーマmusic

NHKもの知り一夜漬けのテーマソング(ミュージック) エンディングテーマ →タイトル 作詞作曲歌手(歌があれば)よろしくお願いします

Aベストアンサー

テーマソングはsweetboxの『Everything's Gonna Be Alright』です。

Q一夜漬け(@_@;)

来週から期末テストなんだけど
ぜんぜん勉強してません( ;∀;)
超ヤバいです(汗)
誰か上手な一夜漬けのやり方を教えてください!
お願いします(>_<)

Aベストアンサー

中学なのか、高校なのか分かりませんが

試験範囲を前もって説明されていると思うので

まず 一通り 目を通しましょう。10ページ進んだら TV見るとか

決めてやるといいと思います。

全教科は無理なので、ノートなどを見返しながら 山をはるしかないです。

理数系はひたすら問題、文系はテキストを何度も読む。これしかないです。

自分のころは、英語のテキストはすべて暗記して、覚えたところから破いてました。

Q一夜漬け…

 私の学校では、今週テストがあります。
 一夜漬けをする必要があるかなぁという気分になって来た所です。
勿論、体に良くない事だとは分かっているけど、勉強に取り込み始める
時期が遅かったのと、要領を掴むのが遅かったのがいけなかったかと
思います。
 一夜漬けをして、覚えないといけない事を覚えられれば良いけど、
次のテストの日に寝坊をしたら意味がありませんよね?実は、昨日と
一昨日も一夜漬けをした(試しにしてみた)のですが、次の日に
いつもの時間に起きる事が出来ませんでした。
 ちなみに、1時間だけ寝るのに、「テレビのオンタイマー」と
「携帯電話の目覚まし時計」と「キッチンタイマー」を使いました。
目覚まし時計は2個あるけど、それは普段から使っても効果がないので
使いませんでした。
 この様な状況にならない様に、事前から準備しておくのが1番良いと
いう事については、分かっています。前の日にとても遅く寝ても、次の
日にきちんと起きられる方法を、上記の他に、何か知っていたら、
教えて頂きたいです。
 宜しくお願い致します。

 私の学校では、今週テストがあります。
 一夜漬けをする必要があるかなぁという気分になって来た所です。
勿論、体に良くない事だとは分かっているけど、勉強に取り込み始める
時期が遅かったのと、要領を掴むのが遅かったのがいけなかったかと
思います。
 一夜漬けをして、覚えないといけない事を覚えられれば良いけど、
次のテストの日に寝坊をしたら意味がありませんよね?実は、昨日と
一昨日も一夜漬けをした(試しにしてみた)のですが、次の日に
いつもの時間に起きる事が出来ませんでした。
...続きを読む

Aベストアンサー

基本的に家に帰ってすぐに寝て起きて勉強を始めると
次の日学校から帰ってくるまでは寝ません。
寝れば忘れてしまうので、寝てから勉強する方が
効率が良いと思います。


人気Q&Aランキング

おすすめ情報