在分析演算法的復雜性的背景下，我試圖圍繞朗道符號的含義。
O在 Big-O-Notation中的正式含義到底是什么？
所以我理解它的方式是O(g(x))給出了一組與 g(x) 一樣快或慢的函式，這意味著，例如在 O(n^2) 的情況下：
例如，其中 t(x) 可以是 x 3 或 x^2 5。我的理解是否正確？
此外，以下符號是否正確？
我看到了一位導師寫的以下內容。這是什么意思？如果 O-Notation 回傳一個集合，你如何使用 less 或 equal？
我也可以寫這樣的東西嗎？
uj5u.com熱心網友回復：
所以我理解它的方式是 O(g(x)) 給出了一組與 g(x) 一樣快或慢的函式。
Big-Oh 符號的這種解釋是正確的。
f(n) = n^2 5n - 2, f(n) 是 O(n^2) 的一個元素
是的，我們可以這么說。O(n^2)用簡單的英語，表示“所有增長速度與 n^2 一樣快或慢于 n^2 的函式的集合”。所以，f(n)滿足這個要求。
O(n) 是 O(n^2) 的子集，O(n^2) 是 O(2^n) 的子集
這個符號是正確的，它來自定義。中的任何功能，也都在O(n)，O(n^2)因為它的增長速度比 慢n^2。2^n是指數時間復雜度，而n^2是多項式。您可以將n^2/的限制2^n設為n無窮大，并證明它O(n^2)是O(2^n)自2^n變大的子集。
O(n) <= O(n^2) <= O(2^n)
這個符號很棘手。正如
這是不正確的：比率只需小于或等于某個固定常數c > 0。
這是正確的版本：
哪里c是一些固定的正實數，它不依賴于n。
例如，f(x) = 3 (n^2)is in ：適用于此的O(n^2)一個常數是。請注意，要求不是“對所有人”，而是“對至少一個常數”cfc = 4c > 0c > 0
你其余的評論都是準確的。該<=運算式中的符號是一種不尋常的用法，但如果<=表示集合包含，則它是正確的。我不會擔心那個表達的意思。
還有其他更微妙的理由來談論“有界”而不是增長率。例如，考慮cosine函式。|cos(x)|在 中O(1)，但它的導數從負一到正一波動，即使x增加到無窮大。
如果你用“增長率”來表示衍生品之類的東西，那么這樣的例子就變得很難談論，但說|cos(x)|是有界的2很清楚。
舉一個更好的例子，考慮
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/434659.html
上一篇：第K個最小數演算法做額外的作業？
下一篇：找到可能的最低分數