理解 Big Oh 符号时出现问题?
Issue while understanding Big Oh notations?
根据 CourseEra 算法课程和 Introduction to Algorithms
,函数 G(n) 其中 n 是输入大小,当存在常量 n0 和 C 时,函数 G(n) 被称为 F(n) 的大 oh 符号,使得此不等式成立
F(n) <= C*G(N)(对于所有 N > N0)
现在,
这个数学定义对我来说很清楚。
但是今天老师教我的,我一头雾水!
他说"Big - Oh Notations are upper bound on a function and it is like the LCM of two numbers i.e. Unique and greater than the function"
我不认为这种说法是正确的,Big Oh 符号真的很独特吗?
此外,
思考 Big Oh 符号,我也困惑自己为什么我们将 Big Oh 符号逼近到最高次项。 (我们可以很容易地证明数学上的不等式,尽管可以选择合适的常数)但是它的真正用途是什么??
我的意思是它意味着什么?
我们甚至可以将 F(n) 作为常数 1 !
的 F(n) 的 Big Oh Notation
我认为它显示了 运行 时间只对最高阶项的依赖!请解开我的疑惑,我可能从书上理解错了,或者我的老师犯了错误?
Is Big Oh notation really unique ?
是也不是。从纯粹的公式来看,Big-O 当然不是唯一的。然而,为了达到其目的,实际上不仅要找到 some 上限,还要找到 lowest 上限。这使得有意义的 "Big-O" 独一无二。
We can even take F(n) as the Big Oh Notation of F(n) for the constant
1 !
是的,我们或许可以做到。但是,Big-O 用于将 类 与 functions/algorithms 相互关联。说 F(n) 与 X(n) 相关,就像 F(n) 与 X(n) 相关一样,这就是您使用 G(n) = F(n) 得到的结果。没什么价值。
这就是为什么我们试图找到唯一的最低 G 来满足方程。 G(n) 通常是一个相当简单的函数,例如 G(n) = n、G(n) = n² 或 G(n) = n*log(n),这使我们能够更轻松地比较算法,因为我们可以很容易地看出,例如,对于所有 n >= something,G(n) = n 小于 G(n) = n²。
有趣的是,对于大 n,大多数算法的复杂度都收敛到一个简单的 G(n)。你也可以说,通过查看大的 n,我们试图将 "important" 从 F(n) 的不那么重要的部分中分离出来;那么我们只需省略 F(n) 中的次要项并得到简化的函数 G(n).
实际上,我们也想从技术细节中抽象出来。例如,如果我有 F(n) = 4*n 和 E(n) = 2*n,我可以为 F 算法使用两倍的 CPU,并且与 E 算法一样好,而不管算法的大小输入。也许一台机器有一个专门的平方根指令,所以 SQRT(x) 是一个单一的步骤,而另一台机器需要更多的指令来获得结果。我们想从中抽象出来。
这也暗示了另一种观点:如果我有问题要解决,例如"calculate x(y)",我可以将解决方案呈现为 "result := x(y)",O(1)。但这不被认为是一种算法。算法的规范必须包括相关的详细程度,以便 a) 有意义和 b) Big-O 可访问。
根据 CourseEra 算法课程和 Introduction to Algorithms ,函数 G(n) 其中 n 是输入大小,当存在常量 n0 和 C 时,函数 G(n) 被称为 F(n) 的大 oh 符号,使得此不等式成立
F(n) <= C*G(N)(对于所有 N > N0)
现在, 这个数学定义对我来说很清楚。
但是今天老师教我的,我一头雾水!
他说"Big - Oh Notations are upper bound on a function and it is like the LCM of two numbers i.e. Unique and greater than the function"
我不认为这种说法是正确的,Big Oh 符号真的很独特吗?
此外, 思考 Big Oh 符号,我也困惑自己为什么我们将 Big Oh 符号逼近到最高次项。 (我们可以很容易地证明数学上的不等式,尽管可以选择合适的常数)但是它的真正用途是什么?? 我的意思是它意味着什么? 我们甚至可以将 F(n) 作为常数 1 !
的 F(n) 的 Big Oh Notation我认为它显示了 运行 时间只对最高阶项的依赖!请解开我的疑惑,我可能从书上理解错了,或者我的老师犯了错误?
Is Big Oh notation really unique ?
是也不是。从纯粹的公式来看,Big-O 当然不是唯一的。然而,为了达到其目的,实际上不仅要找到 some 上限,还要找到 lowest 上限。这使得有意义的 "Big-O" 独一无二。
We can even take F(n) as the Big Oh Notation of F(n) for the constant 1 !
是的,我们或许可以做到。但是,Big-O 用于将 类 与 functions/algorithms 相互关联。说 F(n) 与 X(n) 相关,就像 F(n) 与 X(n) 相关一样,这就是您使用 G(n) = F(n) 得到的结果。没什么价值。
这就是为什么我们试图找到唯一的最低 G 来满足方程。 G(n) 通常是一个相当简单的函数,例如 G(n) = n、G(n) = n² 或 G(n) = n*log(n),这使我们能够更轻松地比较算法,因为我们可以很容易地看出,例如,对于所有 n >= something,G(n) = n 小于 G(n) = n²。
有趣的是,对于大 n,大多数算法的复杂度都收敛到一个简单的 G(n)。你也可以说,通过查看大的 n,我们试图将 "important" 从 F(n) 的不那么重要的部分中分离出来;那么我们只需省略 F(n) 中的次要项并得到简化的函数 G(n).
实际上,我们也想从技术细节中抽象出来。例如,如果我有 F(n) = 4*n 和 E(n) = 2*n,我可以为 F 算法使用两倍的 CPU,并且与 E 算法一样好,而不管算法的大小输入。也许一台机器有一个专门的平方根指令,所以 SQRT(x) 是一个单一的步骤,而另一台机器需要更多的指令来获得结果。我们想从中抽象出来。
这也暗示了另一种观点:如果我有问题要解决,例如"calculate x(y)",我可以将解决方案呈现为 "result := x(y)",O(1)。但这不被认为是一种算法。算法的规范必须包括相关的详细程度,以便 a) 有意义和 b) Big-O 可访问。