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

方法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 – 计算此类算法效率的一般方法是什么？我真的很感激如果你能把我联系到合适的教程……

谢谢