我正在考虑有效的算法来找到一行矩阵中的零个数,但只能想到O(n 2)解(即通过迭代每一行和每列).是否有更有效的方法来计算零？
例如,给定矩阵
3, 4, 5, 6 7, 8, 0, 9 10, 11, 12, 3 4, 0, 9, 10
我会报告有两个零.
tem*_*def 13
没有存储任何外部信息,不,你不能做任何比Θ(N 2)更好的事情.基本原理很简单 - 如果你不查看矩阵中的所有N 2个位置,那么你不能保证你已经找到所有的零并且最终可能会给出错误的答案.例如,如果我知道您查看少于N 2个位置,那么我可以在矩阵上运行您的算法,并查看您报告的零数.然后,我可以查看您未访问的位置,用零替换它们,然后再次运行算法.由于您的算法不会查看这些位置,因此无法知道它们中包含零,因此算法的两次运行中至少有一次会给出错误的答案.
更一般地说,在设计处理数据的算法时,查看是否可以比某些运行时更好的方法是使用这种"对抗性分析".问自己一个问题:如果我跑得比O(f(n))更快,对手是否可以通过改变答案的方式操纵数据,但我无法检测到？这种分析与一些更聪明的数学一起证明,基于比较的排序算法在平均情况下不能比Ω(n log n)做得更好.
如果矩阵具有一些其他属性(例如,如果它已经排序),那么您可能比在O(N 2)中运行做得更好.例如,假设您知道矩阵的所有行都已排序.然后,您可以轻松地在每一行上执行二进制搜索,以确定它包含多少个零,这需要O(N log N)时间并且更快.
根据您的设置参数,如果您假定允许并行扫描,则可以使算法运行得更快.例如,如果您的机器上有K个处理器,专用于扫描矩阵的任务,那么您可以将矩阵拆分为K个大致均匀大小的组,让每个处理器计算组中的零个数,然后将这些计算的结果相加.这最终会给你一个Θ(N 2/K)的运行时间,因为运行时分为多个核心.