Java - 比较两个O(n)算法的效率

Question

我正在学习链表，问题是 - 编写一个函数来打印给定链表的中间项（假设LL有奇数个节点）。

方法1-遍历LL并使用计数器计算节点数。添加1（使其成为偶数），然后将计数器除以2（忽略数学上的差异）。再次遍历LL，但这次只到计数器项，然后返回。

void GetMiddleTermMethod1(){
            //Count the number of nodes
            int counter = 0;
            Node n = FirstNode;
            while (n.next != null){
                counter = counter + 1;
                n = n.next;             
            }
            counter=counter+1/2;
            //now counter is equal to the half of the number of nodes

            //now a loop to return the nth term of a LL 
            Node temp = FirstNode;
            for(int i=2; i<=counter; i++){
                temp = temp.next;
            }
            System.out.println(temp.data);
        }

第二种方法 - 初始化两个节点的引用。一个每次遍历2个节点，另一个只遍历1个节点。当快引用到达null（LL的末尾）时，慢引用将已经到达中间并返回。

void GetMiddleTermMethod2(){
            Node n = FirstNode;
            Node mid = FirstNode;
            while(n.next != null){
                n = n.next.next;
                mid = mid.next;
            }
            System.out.println(mid.next.data);
        }

我有三个问题 -

Q1 - 如果我在面试中被问到如何确定哪种算法效率更高，我该怎么办？我的意思是两个函数都遍历了LL一次半（第二个函数只有一个循环而不是两个循环，但它仍然遍历了LL一次半）...

Q2 - 由于两个算法的大O都是O(n)，哪些参数会决定哪个算法更有效？

Q3 - 计算这种算法的效率的一般方法是什么？如果您能链接到合适的教程，我将非常感激...

谢谢

- satnam

---

我推荐一本书叫做《算法导论》（作者是Thomas H. Cormen）。 - Gabriel Oliveira

我在代码中看到了一些问题 - 比如在你的第二个方法中，如果列表有奇数项（例如3）或1项，你将会遇到问题。为什么不对各种类型的输入运行它并查看结果呢？当两个算法具有相同的渐近复杂度时，通常需要查看其他特征。 - mkobit

Answer 1

嗯，实际上并没有一个简单的答案，答案可能因编译器优化、JIT优化和运行程序的实际机器（可能会因某种原因更好地优化某个算法）而异。

事实是，除了理论上的大O符号给出的渐进行为外，在条件（1）、（2）...（k）下很少有一种“干净、理论”的方法来确定算法A比算法B快。

然而，这并不意味着你无能为力，你可以通过创建各种随机数据集，并计时每个算法所需的时间来进行基准测试。重要的是要多次测试。多少次？直到你使用一些已知和接受的统计检验（例如Wilcoxon符号秩检验）获得统计学显著性。

此外，在许多情况下，不重要的性能通常不值得花时间去优化代码，如果这使代码变得不易读懂 - 因此更难维护，那就更糟了。

- amit

Answer 2

我刚刚在Java中实现了你的解决方案，并在一个包含1111111个随机整数（最大为1000）的链表中进行了测试。结果非常相似：

方法1：

time: 162ms

方法二：

time: 171ms

此外，我想指出您的方法有两个主要缺陷：

方法1：

将counter = counter + 1 / 2;更改为counter =（counter + 1）/ 2;，否则您会得到列表末尾，因为计数器保持不变：）

方法2：

将System.out.println(mid.next.data);更改为System.out.println(mid.data);。

- luuksen

---

太好了！感谢时间分析。我承认第一个缺陷，但不是第二个。while循环将比节点数少执行一次。因此，我打印的是下一个节点而不是mid指向的节点。还是谢谢，没什么大不了的。 - satnam

我不太确定。想象一个由7个项目组成的列表，索引从0到6。你的n和mid一开始都是索引0，3是我们所期望的中间索引。第一轮中，你的n转到索引2，你的mid转到索引1，然后是n[4]和mid[2]，最后是n[6]和mid[3]。这就是我们要获取的索引，而不是下一个索引n[4]。 - luuksen