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 - 初始化2个节点引用.一次遍历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);
        }

我有3个问题 -

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

Q2 - 由于两种算法都具有O(n)的大O,哪些参数将决定哪一种更有效？

Q3 - 计算此类算法效率的一般方法是什么？我真的很感激如果你能把我联系到合适的教程......

谢谢

Answer 1

嗯,没有真正简单的答案,答案可能在编译器优化,JIT优化和运行程序的实际机器上有所不同(由于某种原因,可能会针对一种算法更好地优化).

事实是,除了给我们渐近行为的理论大O符号之外,在条件(1),(2),...中,很少有一种"干净,理论"的方法来确定算法A比算法B快. (K).

但是,这并不意味着您无法做任何事情,您可以通过创建各种随机数据集来对代码进行基准测试,并计算每个算法所用的持续时间.不止一次这样做是非常重要的.还有多少？直到你获得统计学意义,当使用一些已知和接受的统计测试时,如Wilcoxon签名排名测试.

此外,在许多情况下,无关紧要的性能通常不值得花时间来优化代码,如果它使代码的可读性降低,那就更糟了 - 因此更难维护.