存在功課問題。問題是否f(n) = O(h(n))和g(n) = O(h(n))然後f(n) * g(n) = O(h(n))是一個真實的陳述。乘以兩個功能，這兩個功能都是第三個的大O
我一直在研究，我可以提出的最佳答案是它是真實的，但不是所有的時間。我可以拿出一些例子來說明問題，但我有一些問題，如果它是錯誤的。任何人都可以給我一個這樣的例子，或者至少可以指導我一個與我的問題相關的鏈接嗎？任何幫助將不勝感激。
這是不正確的，因爲O(h(n))可能是一個緊密的界限。
例如： f(n) = 2n ∈ O(n)和g(n) = 3n ∈ O(n)。然後f(n) ⋅ g(n) = 6n²但這不是在O(n)。
但是請注意：Big-O是一個上限，這意味着您可以找到函數h(n)這樣就變成了真。對於上面的例子h(n) = n²完成這項工作。
爲了解決這個問題，你可以說：
如果f(n) ∈ O(h(n))和g(n) ∈ O(h(n))，然後f(n) ⋅ g(n) ∈ O(h(n)²)成立。
感謝您的回覆。我正在和我班上的某個人交談，他們也舉了一個類似的例子。我總是發現這些問題的答案比我想的要簡單。 – jmac
歡迎您。這些問題可能會很棘手。你必須仔細看看措辭，然後檢查邊緣情況。 – AbcAeffchen
該聲明總是如此，但它可能有點誤導。這是因爲大O符號不能說明它描述的上界有多緊密。如果你願意，你可以說愚蠢的事情，如f(n) = 1,f(n) = O(n^2)。這樣做並不是很有用，因爲常量函數實際上並不是實際增長的二次方，而是大O符號，它仍然是正確的，因爲多項式函數的確提供了一個常數函數的上界。
f(n) * g(n)的確切上限是O(f(n)) * O(g(n))。如果你選擇h(n)是等於增長最快的O(f(n))，O(g(n))和O(f(n)) * O(g(n))，該語句f(n) = O(h(n))，g(n) = O(h(n))和f(n) * g(n) = O(h(n))都將是真實的，顧名思義漂亮多了。但是你會經常看到有比h更小的功能，它們也限制了一個或多個功能。
如果您想避免big-O符號允許的寬鬆邊界，您可以使用big-Theta（Θ）代替。如果是f(n) = Θ(h(n))，則對於一些c1和c2,c1 * h(n) <= f(n) <= c2 * h(n)對於所有足夠大的值n。也就是說，h(n)既是f(n)的上下漸近界。這個問題中的陳述對於big-Theta範圍來說並不正確（儘管它適用於一些微不足道的情況，例如f和g是常量函數）。
感謝您的回覆。非常感激。 – jmac
@DavidBrossard據我所知，對於SO來說，大O問題是完美的主題，而事實上這對於當前的程序員來說是無關緊要的。 – sclv