【校招VIP】JAVA数据结构----时间复杂度- 校招VIP

转载声明：文章来源https://blog.csdn.net/m0_74760503/article/details/135731894

一、时间复杂度

时间复杂度又被称时间效率，主要衡量的是一个算法的运行速度。算法的时间复杂度是一个数学函数，定量描述了一个算法执行的运行时间。一个算法中所花费的时间与其中语句的执行次数成正比例。语句执行的次数越多，运行的时间就越多。

对给定的算法，求时间复杂度的一般过程是：
n表示输入量的多少
F(n)是问题规模n的某个函数f(n)，记作:
F(n)=O(f(n))
(1) 确定算法问题的规模n，选择基本语句(嵌套最深的语句)
(2) 求其执行次数F(n).
(3）使用大O的渐进表示法O(n)。

大O的渐进表示法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
具体如何使用，看例题。

请计算一下func1基本操作执行了多少次？

public static void func1(int N) {
		int count=0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				count++;  
			}
		}
		for(int k=0;k<2*N;k++) {
			count++;
		}
		int M=10;
		while((M--)>0) {
			count++;
		}
		System.out.println(count);
	}

思路：
首先分别计算每段的执行次数，然后相加。
第一段：问题规模为N，基本语句为count++
循环执行NN次，
第二段：2N;
第三段：因为M=10;所以执行10次。
所以执行基本操作数：F(N)=NN+2N+10;
接下来我们使用大O的渐进表示法来表示时间复杂度
1、用常数1取代运行时间中的所有加法常数。
这里的常数是10，所以把10变成1。F(N)=N^2+2*N+1;
2、在修改后的运行次数函数中，只保留最高阶项。
最高阶：N^2。 F(N)=N^2;
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
此题没有涉及到这步，那么假设一个F(N)=3N^2, 3就是与这个项相乘的常数，所以把去掉就变成了 N^2。
使用大O的渐进表示法以后，Func1的时间复杂度为：O(N^2).

常见时间复杂度计算举例

void func2(int N) {
     int count = 0;
    for (int k = 0; k < 2 * N ; k++) {
          count++;
      }
      int M = 10;
      while ((M--) > 0) {
           count++;
    }
    System.out.println(count);
}

F(N)=2*N+10;
时间复杂度为：O(N)

void func3(int N, int M) {
     int count = 0;
    for (int k = 0; k < M; k++) {
         count++;
}
for (int k = 0; k < N ; k++) {
    count++;
}
System.out.println(count);
}

F(N)=M+N;
有两个未知数M和N， O(M+N)

void func4(int N) {
      int count = 0;
      for (int k = 0; k < 100; k++) {
           count++;
}
   System.out.println(count);
}

基本操作数F(N)=100;
通过大O的渐进表示法的第一步推出：O(1).

func (int n)
{  int  i,j,x=0;
   for(i=1;i<n;i++)//1
      for(j=1;j<=i;j++)//2
            x++;
}

思路：
找到基本语句x++；
设问题规模为n，当i为n时，j=n-1;
i=n-1时，j=n-2,依次类推，最后相加得出F(n)=(1/2)n^2-(1/2)n;根据大O的渐进表示法得出： O(n^2)
扩展：冒泡排序法

void bubbleSort(int[] array) {
      for (int end = array.length; end > 0; end--) {
               boolean sorted = true;
       for (int i = 1; i < end; i++) {
            if (array[i - 1] > array[i]) {
               Swap(array, i - 1, i);
                sorted = false;
               }
        }
      if (sorted == true) {
          break;
          }
       }
}

i=1;
   while(i<=n) 
       i=i*2;//1

思路：问题规模为n,基本语句是1,设其执行次数为t,则：i=2^t,
2^t<=n;
t<=log_2n
所以：O(log_2n)扩展：二分法查找法

int binarySearch(int[] array, int value) {
    int begin = 0;
    int end = array.length - 1;
    while (begin <= end) {
           int mid = begin + ((end-begin) / 2);
          if (array[mid] < value)
             begin = mid + 1;
           else if (array[mid] > value)
               end = mid - 1;
            else
              return mid;
            }
      return -1;
}

int  fact (int n)
{	if  (n<=1) 
  return 1;
   	 else return n*fact(n-1);
}

思路：
设问题规模为1，
当n=1时，F(n)=1;
n>1时，F(n)=F(n-1)+1;
F(n)=F(n-1)+1=F(n-2)+2+…+F(1)+n-1=n;
所以：O(n)

总结：
从上到下，效率由高到低

时间复杂度的几种情况
最坏情况：任意输入规模的最大运行次数(上界) -----我们通常算的就是这个情况
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况（数字在每一个位置的可能性是相同的）：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

二、空间复杂度

空间复杂度又被称空间效率，主要衡量的一个算法所需要的额外空间。。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。