相关疑难解决方法(0)

我更喜欢尽可能少的正式定义和简单的数学.

大多数拥有CS学位的人肯定会知道Big O代表什么.它可以帮助我们衡量算法的实际效率(如何),如果你知道你试图解决的问题属于哪个类别,你可以弄清楚是否仍然可以挤出那么少的额外性能.¹

但我很好奇,你如何计算或近似算法的复杂性？

¹ _{但正如他们所说,不要过度,过早优化是所有邪恶的根源,没有正当理由的优化也应该得到这个名称.}

有没有O(1/n)算法？

或者其他任何小于O(1)的东西？

我很想知道哪种算法更好:

• 具有O(n log n)时间和O(1)空间复杂度的算法
• 具有O(n)时间和O(n)空间复杂度的算法

在O(n long n)时间和恒定空间中求解的大多数算法可以在O(n)时间内通过在空间方面支付罚分来求解.哪种算法更好？我如何决定这两个参数？

示例:数组对总和

1. 可以通过排序在O(n logn)时间内解决
2. 可以在O(n)时间使用散列映射来解决,但是使用O(n)空间