计算算法的复杂性

Question

我不确定这是否是一个有效的问题.

假设有一个O(n ^ 3)算法,它每天用计算能力x对100个数字进行排序.

如果计算能力加倍,即2倍,它将能够排序多少个数字.

我明白我不会定义'计算能力'.如果不明确或错误,请更正问题.

Answer 1

Big O表示法不会给你时间(真正的计算机时间).这是一种尝试理解独立于cpu或其他特定计算机功能的算法效率的方法.

在mathamatics中,你可以说O(n ^ 2)比O(n ^ 3)更有效.但是在工程师观点中,对于n的某些值,O(n ^ 3)可以优于O(n ^ 2).这种方法只是说,对于足够大的n,O(n ^ 2)将比O(n ^ 3)更有效.

在你的管中有一个很好的算法analsysis介绍.第一章有助于解释这些问题: 麻省理工学院6.046J/18.410J算法导论

Big O表示法只能说对于同一台机器,对于足够大的n,O(n ^ 2)优于O(n ^ 3).但对于相同的算法,我认为你不能在计算机功率和输出之间做出直接的比较.如果我们加倍计算机功率,输出加倍？也许是,但可能不是.我想我们不能仅仅通过算法Big O来说出这样的事情.

Answer 2

N = 100可能不够大,无法假设算法已经达到了CPU使用率的渐近行为,因此使用大O表达式来推断更大数据集的CPU使用率可能会产生错误的结果.

但是,您可以尝试确定您是否已经处于渐近区域,测量其他大小(例如,50,80,120等)的数据集的CPU使用率,并查看它们如何适合t = C*N^3曲线,即C a不断待定.

如果在给定N之后拟合"足够好",则可以使用相同的曲线来预测较大数据集的CPU使用率.

在任何情况下,您都应该将这些预测视为计算某些数据集所需的CPU时间的下限,因为在实践中,作为内存,缓存或IO的其他计算资源可能成为CPU使用的瓶颈.

更新:回应Vapuru帖子及其评论:

对于典型的O(N ^ 3)算法,由特定实现执行的操作的数量是t = a + b * N + c * N^2 + d * N^3(可能存在其他组件log N,但正如您将看到的,它实际上并不重要).因此,对于两个给定大小的数据集N1,并N2可以计算t1和t2分别.

对于给定的OP问题,t2 / t1 = 2,所以(a + b * N2 + c * N2^2 + d * N2^3) / (a + b * N1 + c * N1^2 + d * N1^3) = 2和对N1和N2足够大的表达可以近似为(d * N2^3)/(d * N1^3) = 2可以被进一步简化为(N2/N1)^3 = 2等N2 = N1 * 2^(1/3).

这意味着对于大数据集,处理时间加倍(或处理速度加倍并保持时间不变),允许将数据集的大小增加大约一倍2^(1/3),即1.2626%.

实际上,除了CPU速度之外的其他因素可能会影响性能,因此实际应该将其视为N2/N1 < 1.26.