比O（n＆＃xb2;）解决方案更快，可以将所有整数划分总结在数组上
我被赋予了这个代码段作为作业。
int arr[n];
int sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
sum += arr[i] / arr[j];
}
}
假设：N＆LT; 10⁶，ARR中的所有元素均为INT类型，并且小于10⁶
我的任务是比O（n²）时间更快地返回总和。在过去的几个小时中，我一直在考虑这个问题，但我似乎找不到任何方法来加快速度（除了O（（N²+n）/2），我可以通过对数字进行排序并分开来实现这一点而分子大于分母）。
I was given this snippet of code as an assignment.
int arr[n];
int sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
sum += arr[i] / arr[j];
}
}
Assumptions: n < 10⁶, all elements in arr are of type int and are smaller than 10⁶
My task is to return sum faster than O(n²) time. I've been thinking about this for the past few hours and I can't seem to find any way to speed it up (apart from O((n²+n)/2) which I would achieve by sorting the numbers and dividing only while the numerator is larger than the denominator).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
请为我们提供更多代码deatails
，顺便说一句，总的来说，您可以对O（nlogn）进行排序（合并，插入，插入等等），这将是更好的然后o（（n²+n）/2）在运行时项。
please provide us more code deatails
And by the way , in general you can sort in O(nlogn) (merge sort,insertion sort and more) and that will be must better then O((n²+n)/2) in runtime terms.