python - 两种算法的效率比较:查找行/列排序矩阵中的负整数个数
问题描述
以下是完整问题的链接:https ://youtu.be/5dJSZLmDsxk 问题:创建一个函数,返回二维数组中的负整数个数,使得该数组中每一行的整数大小从索引 0 到 n,而每列的整数从上到下都是一样的。例如
{{-5, -4, -3, -2},
{-4, -3, -2, -1},
{-3, -2, -1, 0},
{-2, -1, 0, 1}}
在视频中,CS Dojo 提供了以下解决方案:
def func(M, n, m):
count = 0
i = 0
j = m - 1
while j >= 0 and i < n:
if M[i][j] < 0:
count += j + 1
i += 1
else:
j -= 1
return count
我的问题是:为什么/以下代码效率不高?(唯一的区别是后者从左边开始,并且递增count
多次<--但是这两件事会有什么不同吗?
int rows = 3;
int cols = 4;
int count_neg(const int arrays[rows][cols]) {
int count = 0;
int pos = cols;
for (int i = 0; i < rows; i++) {
for (int j = 0; j <= pos; j++) {
if (arrays[i][j] < 0)
count++;
else {
pos = j;
break;
}
}
if (pos == 0)
break; /*offers miniscule efficiency improvement?*/
}
return count;
}
请假设这些都是用同一种语言编写的。
解决方案
不同之处在于第二个版本扫描所有负数矩阵,并花费O(n*m)时间(整个矩阵可能是负数),而第一个版本跟踪负数和非负数元素之间的边界,并花费O(n+m)时间。
要了解第一个是如何工作的,请考虑:每次迭代都会增加i
或减少j
。 i
只能递增n-1次,并且j
只能递减m-1次。
推荐阅读
- django - 我想检索身份验证代码以使用 python 3 获取 access_token
- excel - 不在搜索字符串中 - 它在搜索字符串中有效
- node.js - 自动分页功能未处理条带节点超时错误?
- excel - 使用与我看到的略有不同的 VBA 范围
- python - 如何在 5 秒后停止此循环?
- c# - 检查用户名是否已经在数据库中
- javascript - lit-html:连接字符串以使用 html``
- python - 如何从 javadoc 注释中删除 { 和 } 之间的 @link 标记及其内容?
- highcharts - Highchart 地图显示了一些已选择的状态,并具有选择其他状态的可行性
- javascript - 如何使用 fetch 发送数组?(Javascript)