問題タブ [big-o]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
big-o - アルゴリズムの目的のための対数の底は何ですか?
時間の複雑さを O(log(N)) と考える場合、対数の底は何ですか?
complexity-theory - このアルゴリズムの複雑さは?
複雑さですか、O(1)
それともO(n)
最良のシナリオですか? シーケンスにはn
要素が含まれています。擬似コードです。
big-o - 私のビッグオーは何ですか?
値を並べ替える私のプログラムは、次の時刻に実行されます。
- 100000 8秒
- 1000000 82s
- 10000000 811s
それはO(n)ですか?
algorithm - 複数のBigOを1つに追加/マージする方法
(たとえば)3つのサブアルゴリズムで構成されるアルゴリズムがある場合、すべて異なるO()特性を持ちます。例:
- アルゴリズムA:O(n)
- アルゴリズムB:O(log(n))
- アルゴリズムC:O(n log(n))
アルゴリズム全体のO()を理論的に推定するにはどうすればよいですか?つまり、それを計時したり、他の実際的な測定を実行したりしません。
よく知られている式や手順はありますか?
algorithm - big-O表記でソートされたリンクリストに挿入する複雑さは何ですか?
big-O表記でソートされたリンクリストに挿入する複雑さは何ですか? 5 つの要素があり、それらすべてを挿入するのは複雑だとしましょう。
どうもありがとうございました
computer-science - 最悪の実行時間 (Big O)
この質問がありますが、理解できないため、解決方法がわかりません。:(
質問は:
プログラム A と B が分析され、最悪の場合の実行時間がそれぞれ 150 n log nとn 2を超えないことがわかりました。次の質問に答えてください。
i) nの値が大きい場合( n > 10000) 、実行時間の保証がより優れているのはどのプログラムですか?
ii) nの値が小さい場合( n < 100)、実行時間の保証がより優れているのはどのプログラムですか?
誰でも私を助けて説明してもらえますか?
algorithm - 二分探索木で合計が 3 番目の数値になる 2 つの数値を見つける
数字の BST が与えられます。a + b = S
O(n) 時間と O(1) 空間で、その中に 2 つの数値 (a, b) を見つける必要があります。
アルゴリズムは何でしょうか?
考えられる方法の 1 つは、BST を二重にリンクされたリストに変換してから、先頭と末尾から開始することです。
または:
performance - グラフ隣接リスト ノード/頂点の O(1) ルックアップを実装する方法。配列?
Adjacency List で実装されたグラフの仕様で、エッジの追加は一定時間で行われると読みました。ただし、O(1) を使用したノード ルックアップが必要になります。最高のパフォーマンスをしたいと思います。ここでの問題は、どのデータ型が私にそれを与えるかということです。ハッシュマップが考慮されていますが、ハッシュマップの最悪のケースはまだ O(n) です。
これに配列を使用できますか? ノードは、任意のデータ型、ジェネリックにすることができます。これは、ノードのみに基づいてインデックス値を生成するハッシュ関数で実行できますか? それは私にO(1)を与えるでしょう。もちろん、LinkedList を indexOf で大文字にして使用することもできます。一定時間は最高です。
algorithm - 長い入力の実行時間を短縮したのはどのようなアルゴリズムですか?
重複の可能性:
O(1 / n)アルゴリズムはありますか?
私は最近さまざまなアルゴリズムを読んでいて、O([n、n ^ 2、log nの組み合わせ)で物事を見ることに非常に慣れています。アルゴリズムが入力を増やすと実行時間が長くなるのはごく普通のことのように思われるので、これはあまり気になりませんが、入力を増やすと実行時間が短くなる有名なアルゴリズムはたくさんありますか?または、たとえば、入力の長さに基づいた定期的な実行時間のような他のアルゴリズムはありますか?
java - 正規表現のパフォーマンスと完全な反復のベストプラクティス
"string".contains("anotherString")
正規表現VSやその他の文字列API呼び出しをいつ使用するかについての一般的なガイドラインがあるかどうか疑問に思いましたか?
上記の決定.contains()
は簡単ですが(1回の呼び出しでこれを実行できるのに、なぜ正規表現に煩わされるのか)、実際の生活ではより複雑な選択が必要になります。たとえば、2回の.contains()
呼び出しまたは1回の正規表現を行う方がよいでしょうか。
私の経験則では、単一のAPI呼び出しで置き換えることができない限り、常に正規表現を使用することでした。これにより、コードが肥大化するのを防ぐことができますが、特に正規表現が大きくなる傾向がある場合は、コードの可読性の観点からはあまり良くありません。
もう1つの、見過ごされがちな議論は、パフォーマンスです。この正規表現に必要な反復回数(「BigO」など)を知るにはどうすればよいですか?完全な反復よりも速いでしょうか?どういうわけか、誰もが正規表現が5if
ステートメントより短く見えると、それはもっと速くなければならないと思い込んでいます。しかし、これは常に当てはまりますか?これは、正規表現を事前にコンパイルできない場合に特に関係があります。