如果 n 的除数之和为 m,则两个数字 n 和 m 称为“友元”
反之亦然。
例如:如果 n = 200 且 m = 284 则
1+2+4+5+10+11+20+22+44+55+110 = 284
1+2+4+71+142 = 220。
所以该方法需要得到一个数字K, 该方法应返回“ friend ”对的数量
如果 K = 9000,则该方法将返回 5,因为有 5 对是“ friend ”:
220,284
1184,1210
2620,2924
5020,5564
6232,6368
就大 O 而言,最有效的运行时间是多少?
最佳答案
虽然我无法告诉您最佳实现的整个算法复杂性,但我可以将其分解,至少对于暴力方法(如果您实现计数器),这样当您调整因式分解方法时,您就知道新的 O 值是多少
第一步:循环遍历数字 0(或 1)-K,这是 O(K) 并对它们应用步骤 2 和 3
第二步:获取数字除数的(和)。如果我们通过循环遍历直到它的所有数字来计算除数,则这是O(K)。
第三步:计算除数和除数之和(说得拗口)是否等于原数O(K)。如果它增加一个计数器。
第四步:输出计数器变量0(1)时间
所以暴力法的整体算法复杂度为O(K*2K) = O(K^2)
关于java - 我的方法的效率有问题。有什么建议吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36669534/