問題タブ [asymptotic-complexity]

複雑さはO（logn）になると思いました。
つまり、内側のループと外側のループの積です -- 100 回を超えて実行されることはないため、省略できます。

私が確信していないのは while 句です。Big-O の複雑さに組み込む必要がありますか? 非常に大きなi値の場合、影響を与える可能性があります。または算術演算は、どのスケールでも問題なく、基本演算としてカウントされ、省略できますか?

質問があり、何度も考え直そうとしましたが、何も得られなかったので、ここに質問を投稿しました。多分私はそれを機能させるために、他の人の視点を得ることができます...

問題は、奇数回発生する 1 つを除いて、偶数回発生する値のコレクションで構成される SORTED 配列が与えられることです。log n 時間で解を見つける必要があります。

O(n) 時間で解を見つけるのは簡単ですが、log n 時間で実行するのはかなり難しいようです。

Big O（1）であるが、Ω（1）ではない関数、およびその逆の関数を手伝ってくれる人はいますか？いくつかの説明が大いに役立ちます。

私はプログラミングの初心者で、最近、漸近的複雑さのトピックを紹介されました。私が興味を持っているのは、要素の数とそれらの並べ替えにかかる時間を考慮して、並べ替え方法の漸近的な複雑さをどのように把握するかということです。

これが私の言いたいことの例です。

• 「sortArray」が 400 要素のソート済み配列をソートする時間: 4
• 「sortArray」が 800 要素のソート済み配列をソートする時間: 8
• 「sortArray」が 1600 要素のソート済み配列をソートする時間: 16

• 「sortArray」が 3200 要素のソート済み配列をソートする時間: 26

• 「sortArray」が 400 要素のランダム配列をソートする時間: 255

• 「sortArray」が 800 要素のランダム配列をソートする時間: 958
• 「sortArray」が 1600 要素のランダム配列をソートする時間: 4059
• 「sortArray」が 3200 要素のランダム配列をソートする時間: 16585

このようなものの Big O 表記を計算する方法について何か助けはありますか? ありがとう！

次の例を証明したいと思います。

多項式関数が指数関数よりも速く成長することは注目に値します。条件を満たす k0 > 0 を見つけようとします。

よりも

したがって、k0 > 0、正で十分に小さいですが、c の値は関係ありません... OK ですか?

私はかなり長い間、RTOS および Linux ドライバーの開発に取り組んできました。現在、私は半導体企業で面接を受けていますが、文字列のアルゴリズム、および時間と空間の複雑さに関する質問に答えることができません。私は電子工学のバックグラウンドを持っているため、個別の数学やアルゴリズムを勉強したことはありません。

このギャップをどのように克服できますか？

あなたが猫のいる高層ビルにいると想像してみてください。猫は低層の窓からの落下に耐えることができますが、高層階から投げられると死にます。最小の試行回数で、猫が生き残ることができる最長の落下をどのように把握できますか？

明らかに、猫が1匹しかない場合は、直線的にしか検索できません。まず1階から猫を投げます。それが生き残った場合は、2番目から投げます。最終的に、f階から投げ出された後、猫は死にます。次に、フロアf-1が最大の安全フロアであることがわかります。

しかし、複数の猫がいる場合はどうなりますか？これで、ある種の対数探索を試すことができます。ビルドに100階があり、2匹の同じ猫がいるとします。最初の猫を50階から投げ出して死んだ場合、50階を直線的に検索するだけで済みます。あなたが最初の試みのために低い階を選ぶならば、あなたはさらに良くすることができます。一度に20階の問題に取り組むことを選択し、最初の致命的な階が＃50であるとしましょう。その場合、最初の猫は20階と40階からの飛行を生き延びてから、60階で死にます。41階から49階までを個別に確認する必要があります。これは合計12回の試行であり、バイナリ除去を使用しようとした場合に必要となる50回よりもはるかに優れています。

一般的に、2匹の猫がいるn階建ての建物にとって、最善の戦略と最悪の場合の複雑さは何ですか？n階とm猫はどうですか？

すべての猫が同等であると仮定します。それらはすべて、特定のウィンドウからの落下で生き残るか、死ぬでしょう。また、すべての試みは独立しています。猫が転倒を生き延びた場合、それは完全に無傷です。

これは宿題ではありませんが、学校の課題で一度解決したことがあるかもしれません。今日頭に浮かんだのは気まぐれな問題で、解決策を覚えていません。誰かがこの問題または解決策のアルゴリズムの名前を知っている場合、ボーナスポイント。

「アルゴリズムAの最悪の場合の実行時間」と「アルゴリズムAの実行時間はO(n)」というステートメントに違いはありますか?

私が「違いはない」と思うのは、最悪の場合は関数がかかるピーク実行時間であり、O(n) は関数が「制限されている」ことを意味するためです。どちらも同じ意味です。

私の論理が正しいことを願っています。

OはBig-Oを表します。

O(g) : { f| f は負でない関数です
             c,m が存在します。ここで、c と m は
             、すべての n >= m に対して f(n) <= cg(n) となる任意の定数です }

           Show That :- O( f(n) + g(n ) ) = O( max{ f(n) , g(n) } ) .

ここと math.stackexchange の両方で Big-Oh に関する質問と回答を読むのに多くの時間を費やしましたが、math.stackexchange はこの種の質問を好まないように見えるため、これが最適な場所のようです。それで、私は CS コースの大学でいくつかのコースワークを与えられましたが、それを完全には理解していません。皆さんが助けてくれることを望んでいました. 「宿題」の質問はここでは少し嫌われていることを理解しているので、私のコースワークの一部ではありませんが、同様のスタイルの別の例を選択しました.

だから、ここに私がメモで与えられた定義があります：

そして、私が与えられた質問は次のとおりです。

定義 2.5 を使用して、f(n) が O(g(n)) の場合、k + f(n) も O(g(n)) であることを示します。

このような問題に対するあらゆる種類の回答を求めて、3 日間 Web を検索しました。定義 2.5 を見ると、f(n) は O(g(n)) であり、k + f(n) は O(g(n)) であると書かれています。私にはそれで十分ですが、それがどのように導出されたかを証明する必要があるようです. 私は最初は誘導によって何とかすべきだと思っていましたが、それ以来、それに反対することに決めました.もっと簡単な方法があるに違いありません.

どんな助けでも大歓迎です。誰かが率直に答えてくれるとは思っていません。方法論か、これを行うためのテクニックを学べる場所への参照のどちらかを好むでしょう。これは私の実際のコースワークではなく、同様のスタイルの問題であることをもう一度思い出していただけますか。

前もって感謝します。