python - 计数 1's in a n x n array of 0' 和 1

Question

假设在数组的每一行中，所有 1 都在 0 之前，我如何才能想出 (O)nlogn 算法来计算数组中的 1。我想首先我必须制作一个计数器，在每一行中搜索 1 (n)，然后将其添加到计数器中。 “log n 部分”在哪里发挥作用？我读到执行此操作的递归算法具有 nlogn 复杂性，但我不太确定我将如何执行此操作。我知道如何使用 for 循环在 O(n^2) 中执行此操作。伪代码或提示会有所帮助!谢谢

Answer 1

由于所有 1 都在 0 之前，您可以使用二进制搜索算法(即 log N)找到第一个 0 的索引，您只需对所有 N 行执行此操作。所以总的复杂度是 NlogN。