kos*_*osh 3 arrays algorithm big-o list
我很难绕着大O符号进行配对操作.问题非常简单 - 为数组中给定的数字列表生成所有可能的对.
我的第一个猜测是有一个嵌套的for/foreach循环并生成对.这很容易,我得到的每一个,我分析其他数字,这给了我一个复杂的n ^ 2.
现在,如果我尝试进一步优化它并说(1,4)与(4,1)相同,那么对于像1,2,3,4,5那样的排序数组.我只以这种方式在嵌套for循环中运行配对操作
for (i =0; i < count; i++) {
for (j = i + 1; j < count - 1; j++)
}
}
在这种情况下,我只运行数组<n ^ 2次.对于7个数字的样本大小,我遍历循环21次以生成对.我知道这不能是一个log-n操作,我很想说这个操作会收敛到n ^ 2,但我不记得我的数学或理论课程中的确定答案.我该如何解决这个问题？
上下文:我接受了一个类似问题的采访,这是出于我与朋友的争论,如果列表中的配对操作总是优于n ^ 2.
你做的少于n 2次是正确的.问题是你正在做多少手术.
让我们考虑阵列中有多少对.如果n个数中的每一个都可以与(n-1)个其他数字配对,则可能的对的总数是n(n-1).原始for循环的每次迭代都会生成其中一对,因此生成的对的总数为n 2 - n,即O(n 2).
现在,如果通过说(1,4)和(4,1)相同来消除重复对,那该怎么办？在这种情况下,请注意您生成的一半对将是无关的 - 您将生成每对两次.这意味着对的数量是(n 2 -n)/ 2.这个表达式小于n 2,但是注意它仍然是O(n 2),因为big-O表示法忽略常量.
换句话说 - 你生成的数量少于n 2对是正确的,但是你创建的对的总数仍然是O(n 2).
更一般地说 - 如果你通过一些常数因素减少算法所做的总工作量(比如,你将工作量削减了一半,或者将工作减少了100倍),你就没有改变大O运行时算法.Big-O完全忽略了常量.为了减少big-O运行时间,您需要将工作总量减少一个超过常量的量; 比如,系数为n,log n等.
希望这可以帮助!