有没有什么情况下你更喜欢O(log n)时间复杂度而不是O(1)时间复杂度?还是O(n)到O(log n)
你能举个例子吗?
有没有什么情况下你更喜欢O(log n)时间复杂度而不是O(1)时间复杂度?还是O(n)到O(log n)
你能举个例子吗?
当前回答
选择大O复杂度高的算法而不是大O复杂度低的算法的原因有很多:
most of the time, lower big-O complexity is harder to achieve and requires skilled implementation, a lot of knowledge and a lot of testing. big-O hides the details about a constant: algorithm that performs in 10^5 is better from big-O point of view than 1/10^5 * log(n) (O(1) vs O(log(n)), but for most reasonable n the first one will perform better. For example the best complexity for matrix multiplication is O(n^2.373) but the constant is so high that no (to my knowledge) computational libraries use it. big-O makes sense when you calculate over something big. If you need to sort array of three numbers, it matters really little whether you use O(n*log(n)) or O(n^2) algorithm. sometimes the advantage of the lowercase time complexity can be really negligible. For example there is a data structure tango tree which gives a O(log log N) time complexity to find an item, but there is also a binary tree which finds the same in O(log n). Even for huge numbers of n = 10^20 the difference is negligible. time complexity is not everything. Imagine an algorithm that runs in O(n^2) and requires O(n^2) memory. It might be preferable over O(n^3) time and O(1) space when the n is not really big. The problem is that you can wait for a long time, but highly doubt you can find a RAM big enough to use it with your algorithm parallelization is a good feature in our distributed world. There are algorithms that are easily parallelizable, and there are some that do not parallelize at all. Sometimes it makes sense to run an algorithm on 1000 commodity machines with a higher complexity than using one machine with a slightly better complexity. in some places (security) a complexity can be a requirement. No one wants to have a hash algorithm that can hash blazingly fast (because then other people can bruteforce you way faster) although this is not related to switch of complexity, but some of the security functions should be written in a manner to prevent timing attack. They mostly stay in the same complexity class, but are modified in a way that it always takes worse case to do something. One example is comparing that strings are equal. In most applications it makes sense to break fast if the first bytes are different, but in security you will still wait for the very end to tell the bad news. somebody patented the lower-complexity algorithm and it is more economical for a company to use higher complexity than to pay money. some algorithms adapt well to particular situations. Insertion sort, for example, has an average time-complexity of O(n^2), worse than quicksort or mergesort, but as an online algorithm it can efficiently sort a list of values as they are received (as user input) where most other algorithms can only efficiently operate on a complete list of values.
其他回答
选择大O复杂度高的算法而不是大O复杂度低的算法的原因有很多:
most of the time, lower big-O complexity is harder to achieve and requires skilled implementation, a lot of knowledge and a lot of testing. big-O hides the details about a constant: algorithm that performs in 10^5 is better from big-O point of view than 1/10^5 * log(n) (O(1) vs O(log(n)), but for most reasonable n the first one will perform better. For example the best complexity for matrix multiplication is O(n^2.373) but the constant is so high that no (to my knowledge) computational libraries use it. big-O makes sense when you calculate over something big. If you need to sort array of three numbers, it matters really little whether you use O(n*log(n)) or O(n^2) algorithm. sometimes the advantage of the lowercase time complexity can be really negligible. For example there is a data structure tango tree which gives a O(log log N) time complexity to find an item, but there is also a binary tree which finds the same in O(log n). Even for huge numbers of n = 10^20 the difference is negligible. time complexity is not everything. Imagine an algorithm that runs in O(n^2) and requires O(n^2) memory. It might be preferable over O(n^3) time and O(1) space when the n is not really big. The problem is that you can wait for a long time, but highly doubt you can find a RAM big enough to use it with your algorithm parallelization is a good feature in our distributed world. There are algorithms that are easily parallelizable, and there are some that do not parallelize at all. Sometimes it makes sense to run an algorithm on 1000 commodity machines with a higher complexity than using one machine with a slightly better complexity. in some places (security) a complexity can be a requirement. No one wants to have a hash algorithm that can hash blazingly fast (because then other people can bruteforce you way faster) although this is not related to switch of complexity, but some of the security functions should be written in a manner to prevent timing attack. They mostly stay in the same complexity class, but are modified in a way that it always takes worse case to do something. One example is comparing that strings are equal. In most applications it makes sense to break fast if the first bytes are different, but in security you will still wait for the very end to tell the bad news. somebody patented the lower-complexity algorithm and it is more economical for a company to use higher complexity than to pay money. some algorithms adapt well to particular situations. Insertion sort, for example, has an average time-complexity of O(n^2), worse than quicksort or mergesort, but as an online algorithm it can efficiently sort a list of values as they are received (as user input) where most other algorithms can only efficiently operate on a complete list of values.
当O(1)中的“1”工作单元相对于O(log n)中的工作单元非常高,且期望集大小较小时。例如,如果数组中只有两到三个项,那么计算Dictionary哈希码可能比迭代数组要慢。
or
当O(1)算法中的内存或其他非时间资源需求相对于O(log n)算法非常大时。
给已经好的答案锦上添花。一个实际的例子是postgres数据库中的哈希索引和b树索引。
哈希索引形成一个哈希表索引来访问磁盘上的数据,而btree顾名思义使用的是btree数据结构。
大O时间是O(1) vs O(logN)
目前不鼓励在postgres中使用哈希索引,因为在现实生活中,特别是在数据库系统中,实现无冲突的哈希是非常困难的(可能导致O(N)最坏情况的复杂性),正因为如此,使它们具有崩溃安全性就更加困难了(在postgres中称为提前写日志- WAL)。
在这种情况下进行这种权衡,因为O(logN)对于索引来说已经足够好了,而实现O(1)非常困难,而且时间差并不重要。
人们已经回答了你的确切问题,所以我要回答一个稍微不同的问题,人们来这里时可能会想到这个问题。
许多“O(1)时间”算法和数据结构实际上只需要预期的O(1)时间,这意味着它们的平均运行时间是O(1),可能仅在某些假设下。
常见的例子:哈希表,“数组列表”的扩展(也就是动态大小的数组/向量)。
在这种情况下,您可能更喜欢使用保证时间绝对受对数限制的数据结构或算法,即使它们的平均性能可能更差。 一个例子可能是平衡二叉搜索树,它的运行时间平均较差,但在最坏的情况下更好。
在n有界且O(1)算法的常数乘子高于log(n)上的界的任意点。例如,在哈希集中存储值是O(1),但可能需要对哈希函数进行昂贵的计算。如果数据项可以简单地进行比较(相对于某些顺序),并且n的边界是这样的,log n明显小于任何一项上的哈希计算,那么存储在平衡二叉树中可能比存储在哈希集中更快。