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

Question

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

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

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 - 初始化对节点的 2 个引用。一个一次遍历 2 个节点，另一个仅遍历 1 个节点。当快速引用达到零（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);
        }

我有3个问题 -

Q1 - 如果我在求职面试中被问到这个问题，我怎么知道哪种算法更有效？我的意思是这两个函数都遍历 LL 一次半（第二个函数在一个循环中完成而不是 2 次，但它仍然遍历 LL 一次半）......

问题 2 - 由于两种算法都有 O（n） 的大 O，哪些参数将决定哪一种更有效？

问题 3 - 计算此类算法效率的一般方法是什么？如果您能将我链接到合适的教程，我将不胜感激......

谢谢

Answer 1

好吧，没有真正简单的答案，答案可能因编译器优化、JIT 优化和运行程序的实际机器而异（由于某种原因，它可能针对一种算法进行了更好的优化）。

事实是，除了给我们渐近行为的理论大O符号之外，很少有"干净的，理论上的"方法来确定算法A在条件（1），（2）,...,（k）中比算法B更快。

但是，这并不意味着您无能为力，您可以通过创建各种随机数据集以及每种算法所花费的持续时间来对代码进行基准测试。不止一次这样做非常重要。还有多少？直到你得到一个统计显著性，当使用一些已知和接受的统计检验时，如Wilcoxon符号排名检验。

此外，在许多情况下，微不足道的性能通常不值得花时间优化代码，如果它使代码的可读性降低，因此更难维护，情况会更糟。

Answer 2

我刚刚实现了您的解决方案 i java 并在 1.111.111 个随机整数的 LinkedList 中对其进行了测试，最多 1000 个。结果非常相似：

方法一：

time: 162ms

方法2：

time: 171ms

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

方法一：

将counter = counter + 1 / 2;更改为counter = (counter + 1) / 2;否则，您将获得列表的末尾，因为计数器仍然是计数器:)

方法2：

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