我试图在PC上运行程序的背景下理解Big O分析的一个特定方面.
假设我有一个性能为O(n + 2)的算法.如果n变得非常大,那么2变得微不足道.在这种情况下,非常清楚真正的性能是O(n).
但是,另一种算法的平均性能为O(n ^ 2/2).我看到这个例子的书说实际表现是O(n ^ 2).我不确定我明白为什么,我的意思是在这种情况下,2似乎并非完全无足轻重.所以我正在寻找书中一个很好的清晰解释.这本书以这种方式解释:
"考虑1/2意味着什么.检查每个值的实际时间高度依赖于代码转换的机器指令,然后取决于CPU执行指令的速度.因此1/2不会非常意思."
我的反应是......嗯??? 我完全不知道那句话是什么,或者更确切地说,这句话与他们的结论有什么关系.请允许有人为我拼出来.
谢谢你的帮助.
在下面的视频中描述了一些渐近分析问题:https: //class.coursera.org/algo-004/lecture/169
但我无法理解"低阶词"和"常数因子"本身是什么？(这是视频的第4分钟).
合并排序是6n*log2(n)+6n.为什么6n视频和6中提到的情况下的低阶词是constant factor？这些术语有具体的定义吗？
例如，我在下面提到了功能的输入和输出 reverseWords()
这是一个简单的示例，但这将有助于我理解。我如何为下面的请求编写O（1）空间中的函数？
// var input = ['H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r'];
// Output(same array): ['o', 'l', 'l', 'e', 'H', ' ', 'r', 'o', 'w']
// In O(1) space complexity
function reverseWords(input) {
}
reverseWords(input);
我将如何编写O（1）空间中的函数？例如 -
function reverseString(str) {
return str.split('').reverse().join('');;
}
reverseString("hello world");
这是O（1）空间复杂度吗？我已经提到了这是什么O（1）空间复杂度？但在对javascript的实际理解方面仍然存有疑问。