时间复杂度+链表相交判断

1、如何计算算法的时间复杂度

 

在计算算法时间复杂度时有以下几个简单的程序分析法则:

1.对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间

2.对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"

    求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)

 

=O(g(n)),则          T1(n)+T2(n)=O(max(f(n), g(n)))

特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))

3.对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用

 

的时间,需注意的是检验条件也需要O(1)时间

4.对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验

 

循环条件的时间耗费,一般可用大O下"乘法法则"

    乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2

 

(n)=O(g(n)),则          T1*T2=O(f(n)*g(n))

5.对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法

 

法则技术整个算法的时间复杂度

另外还有以下2个运算法则:

(1)   若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))

(2)   O(Cf(n)) = O(f(n)),其中C是一个正常数

可以用以上法则对下面程序段进行简单分析

①for (i=0; i<n; i++)

②    for (j=0; j<n; j++)

        {

③       c[i][j] = 0;

④       for (k=0; k<n; k++)

⑤           c[i][j]= c[i][j]+ a[i][k]* b[k][j];/ * T5(n) = O(1) */

        }

第①条与②③④⑤是循环嵌套T1(n)*T2(n)* (T3(n)+ T4(n)* T5(n))= O(n*n*n)

 

即为整个算法的时间复杂度

O(1)<O(log2n)<O(n)<O(n log2 n)<O(n^2)<O(n^3)<O(2^n)

 

2、判断两个链表是否相交（来自《编程之美》）：

 在两个链表没有环的前提下，如何判断两个链表是否相交？

 

解法一:嵌套循环，判断第二个链表的每个节点是否在第一个链表中。时间复杂度O(n^2)  也可写、成(O(len(n1)+len(n2))).

 

解法二:将第一个链表的所有节点存在hash表中（按地址存），遍历第二个节点判断是否在hash表中。时间复杂度：O(n)，空间复杂度O(n)。

 

解法三：将第一个链表的末节点接在第二个链表的头部。然后从第二个链表开始遍历看是否能回到第二个链表的头部，如果能就说明两个链表相交了。如图：

 时间复杂度：O(n),因为需要保存第一个节点的末节点（为了恢复现场）和第二个链表的首节点，空间复杂度是常数O(1)。

 

解法四：如果两个链表有相交的话，最后末节点必须相同。所以首先遍历第一个节点，记忆末节点；然后遍历第二节点，判断末节点是否相同。时间复杂度O(n),而空间的消耗只要存末节点的空间而已。

 

显然，以上算法中解法四相对优异。

 

如果，问题变为：

 

1、链表可能有环，该怎么调整？

链表有环，末节点的下一个节点肯定在链表内部。所以，不管有没有环，先断开末节点的指向，也就是将末节点指向NULL，然后判断第二个链表的末节点和第一个链表是否相同（也即是上面的解法四）。

 

 2、求出第一个相交的节点

分两步：  a  不管有没有环，先将末节点指向NULL变为无环

              b   用上面的解法二，找出出现第一个出现在hash表中的节点。