AMAZON OA2 新的一个coding题！！！

dwl1222 发表于 2015-9-25 06:36
public class process {
        int arriveTime;
        int excuteTime;

请问你的代码 的时间复杂度是O(n^2) 吗？我不太确定 所以想请教一下

熊亮亮111 发表于 2015-11-18 03:02
请问你的代码 的时间复杂度是O(n^2) 吗？我不太确定 所以想请教一下

我觉得并不是。不是说有两个循环就是n^2的。你仔细看代码: 里面的nextProIdx是一直在增加的。本质上就是把每个process加入queue在一个个处理的过程。应该是线性的。 如果要量化的话。时间复杂度应该等于 Sum(ceiling(execute[i] / q))  0<=i < execute.length.
看看这个连接会帮助你理解https://en.wikipedia.org/wiki/Round-robin_scheduling

dwl1222 发表于 2015-11-18 05:20
我觉得并不是。不是说有两个循环就是n^2的。你仔细看代码: 里面的nextProIdx是一直在增加的。本质上就是 ...

看着你的头像实在是让我分心啊。 我跟朋友讨论了一下，又觉得是O(n),for循环里边就是把没有执行的任务添加到queue里， 然后while里边再取出来执行， 所以一共n个任务 O(n)

熊亮亮111 发表于 2015-11-18 08:35
看着你的头像实在是让我分心啊。 我跟朋友讨论了一下，又觉得是O(n),for循环里边就是把没有执行的任务添 ...

哈哈。头像美吧，竟然没被封。。 你说得对。是线性的复杂度。但是至于n是多少不取决于任务的个数。二是取决于每个任务的时长。因为每完成的任务会被继续加到队尾。
需要讨论的画家我威信把。这论坛好不方便。dingweilong002

https://www.youtube.com/watch?v=aWlQYllBZDs

这里有视频介绍的很清楚！Round Robin Algorithm Tutorial (CPU Scheduling)

楼主好人求截图！

lz给的截图为什么结果是1秒？我算的是1.25秒？是不是题的返回值是整形的？

novac812 发表于 2015-11-17 08:06
第二个图，发在这里啦。

lz请问这为什么是1秒？我算的是1.25秒？

dwl1222 发表于 2015-9-25 06:36
public class process {
        int arriveTime;
        int excuteTime;

我跑你的程序，结果是8.6666  不知道为啥。。

补充内容 (2015-12-4 00:40):
我找到原因了，是因为我把class 都改成了static 然后跑的，结果就是8.6666666.  但是不改的话就是2.333333了。 求问这又是为什么呢。。

补充内容 (2015-12-4 00:44):
搞明白了，是我不小心多删了代码


补充内容 (2015-12-4 00:44):
搞明白了，是我不小心多删了代码


补充内容 (2015-12-4 00:44):
搞明白了，是我不小心多删了代码

vieri3221 发表于 2015-12-4 00:37
我跑你的程序，结果是8.6666  不知道为啥。。

补充内容 (2015-12-4 00:40):

。。。自言自语