問題タブ [big-o]

これO(N)ですかO(1)？なぜ？

重複の可能性:
O(1/n) アルゴリズムはありますか?

あなたのコードが O(1) 未満の Big O になる可能性はありますか?

有限集合からランダムな値を取得することに関する この質問は、私に考えさせました...

Y値のセットからX個の一意の値を取得したいという人はかなり一般的です。たとえば、カードのデッキから手を配りたい場合があります。私は5枚のカードが欲しいです、そして私はそれらがすべてユニークであることを望みます。

今、私はこれを素朴に行うことができます。ランダムなカードを5回選び、複製を取得するたびに、5枚のカードを取得するまで再試行します。ただし、これは、大きなセットからの多数の値の場合はそれほど大きくありません。たとえば、1,000,000のセットから999,999の値が必要な場合、このメソッドは非常に悪くなります。

問題は、どれほど悪いのかということです。O（）値を説明してくれる人を探しています。x番目の数を取得するにはy回の試行が必要です...しかし、いくつですか？任意の値についてこれを理解する方法を知っていますが、シリーズ全体でこれを一般化し、O（）値を取得する簡単な方法はありますか？

（問題は、「これをどのように改善できるか」ではありません。これは、修正が比較的簡単であり、他の場所でも何度も取り上げられていると確信しているためです。）

私が使用した擬似コード：

私の理解によると：

• 1行目：実行V-1回数。
• 2行目：すべての頂点の次数の合計時間…..つまり2E時間

2行目ごとに2行目と4行目は、すべてのエッジを1つずつlog E追加/削除しているため、時間がかかります。PQ

したがって、合計time= V-1+2E.logE=E.log E

しかし、本はそれがそうだと言っていE.logVます、それがなぜであるか説明できますか？

私はこのメソッド isPalindrome() を持っており、その時間の複雑さを見つけようとしています。また、コードをより効率的に書き直そうとしています。

これで、このコードが文字列の文字をチェックして、前の文字と同じかどうかを確認し、同じ場合は bP を変更しないことがわかりました。

時間の複雑さを O(N + 3) にすると思いますか? これは正しいです。

また、これをより効率的にするために、文字を一時的な文字列に格納するとよいでしょうか?

行を含むテーブルで、結果nを返したいSQL 選択の Big-O とは何ですか?m

Update、またはdelete、またはCreate操作の Big-O とは何ですか?

私は一般的にmysqlとsqliteについて話しています。

Big-O表記O(n)とLittle-O表記の違いは何o(n)ですか?

Big-Oh記法について学び始めています。

与えられた関数のC と N ₀を見つける簡単な方法は何ですか?

たとえば、次のように言います。

(n+1) ⁵、または n ⁵ +5n ⁴ +10n ² +5n+1

Big-Oh の正式な定義は次のとおりです。

f(n) と g(n) を、非負の整数を実数にマッピングする関数とします。すべての整数 N > に対して f(n) <= cg(n)となる実定数 c > 0 と整数定数 N ₀ >= 1 がある場合、f(n) は O(g(n)) であると言います。 N ₀。

_{私の質問は、c と N 0}の値を選択するための優れた確実な方法は何ですか?

(n+1) ⁵を超える与えられた多項式について、それが O(n ⁵ ) であることを示さなければなりません。では、推測せずに上記の定義を真にするには、c と N ₀をどのように選択すればよいでしょうか?

これは厳密にはプログラミングの質問ではないことはわかっていますが、コンピューター サイエンスの質問であるため、誰かが私を助けてくれることを願っています。

私はアルゴリズムの宿題に取り組んでおり、いくつかのアルゴリズムの Big-Oh、Big-Omega、Theta などを考え出しています。私はそれらの C 値と N ₀値を見つけることによってそれらを証明していますが、すべてうまくいっています。

しかし、私はセットの最後の 2 つの問題に遭遇し、その方法を理解するのに苦労しています (そして、Google はあまり役に立ちません)。

これまで、合計の Big-Oh/Omega を理解する必要はありませんでした。

私の最後の2つの問題は次のとおりです。

• ^{i 2}のΣ(i=1～n)がO(N ³ ) であることを示せ

と

• _{[log 2} i]のΣ(i=1～n)がΩ(n log n)であることを示せ

私の質問は、どうすればそれを示すことができますか?

たとえば、最初のものでは、直感的に、i ²の合計が O(N ³ ) であることがわかりません。2番目のものは私をさらに混乱させます。誰かがこれらの合計の Big-Oh と Big-Omega を表示する方法を説明できますか?

私は 3 つの関数を持っています:とf(n)=2nlog ⁽ logはbase 2 です)。g(n)=n!h(n)=n(n)(n)

f(n)との比較g(n): 階乗関数は、(上限が低い)g(n)として近似できます。これを考えると、 ですか？O(nn)g(n)=Ω(f(n))

と とg(n)とをどのように比較しますか?h(n)f(n)h(n)