Loading...
墨滴

公众号:offer多多

2021/08/17  阅读:41  主题:橙心

吃土记:之前理解理解时间复杂度计算方式是错误的

问题还原

《算法导论》9.2:快速选择 时间复杂度是o(n),

这个认识不对呀,快速排序时间复杂度o(nlogn)都记忆多少次了

敲黑板:吃土记:之前理解时间复杂度计算方式是错误的。

  • 堆排序中建堆过程的时间复杂度O(n)
  • 快速选择 时间复杂度是o(n)

查缺补漏

  • 时间复杂度 定义:

若有某个辅助函数f(n), 使得当n趋近于无穷大时,

敲黑板 T(n)/f(n)的极限值为不等于零的常数,

则称f(n)是T(n)的同数量级函数。 记作T(n)=O(f(n))

  • 根据定义,可以归纳出基本的计算步骤
  1. 计算出基本操作的执行次数T(n)

  2. 计算出T(n)的数量级

  3. 用大O来表示时间复杂度

O(n)

  • 代码
   a=0;
   b=1;                     ①
   for (i=1;i<=n;i++) ②
   {  
      s=a+b;    ③
      b=a;     ④  
      a=s;     ⑤
   }
  •    语句1的频度:1,        
       语句2的频度:n,        
       语句3的频度:n,        
       语句4的频度:n,    
       语句5的频度:n,  
    
         T(n) = 1+4n
         f(n) = n
         lim(T(n)/f(n)) = 1*(1/n) + 4 = 4
        
         T(n) = O(n)

O(n2)

敲黑板:

  • 代码1
void aFunc(int n) {
// 第一部分时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
  for(int j = 0; j <= n; j++) {
    printf("Hello, World!\n");
  }
}
  • O(n × n × 1),即 O(n^2)。

  • 代码2

   for (i=0;i<n;i++)
   { 
       for (j=i;j<=n;j++)    
         printf("Hello, World!\n");    
   }  
   
  • 等差数列 n +n-1+n-2+2+1 =(n+1)(n)/2

O(log2n)

method6(int n){
    while((n=n/2)>0){
        System.out.println("葵花宝典");
    }
}
/*
假如:n=8 ; 8/2=4 执行1次;4/2=2 执行1次;2/2=1 执行1次;1/2=0.5=0 执行判断后,不进入循环体。
    所以循环体执行3次,判断执行3+1次;2^3=8---->log2(8)=3
    n=16 ; 16/2=8 执行1次;8/2=4 执行1次;4/2=2 执行1次;2/2=1 执行1次;
    所以循环体执行4次,判断执行4+1次;2^4=16---->log2(16)=4

    所以时间复杂度:log2(n)+(log2(n)+1) = 2log2(n)+1
    log2(n):循环体内执行次数,(log2(n)+1):判断语句执行次数
*/

总结

用大O表示法如下:

method1: 1+1+1 = 3   即O(1)
method2: 1+(5+1)+5+5 = 17   即O(1)

method3: 3n+2   即O(n)

method4: 3n^2+4n+2   即O(n^2)
method5: 49n+2   即O(n)

method6: 2log2(n)+1   即O(logn)

method7: 2log5(n)+1   即O(logn)

method8: 2nlog2(n)+4log2(n)+2   即O(nlogn)

method9: 2n+2+4*((1/2)n^2+(1/2)n)+1   即O(n^2)

应用

堆排序中建堆过程的时间复杂度O(n)

其实,建堆的整个过程中一个节点的比较次数是与它的高度k成正比的,

所以,我们可以得出 第h层的元素有1个,它最多需要比较(h-1)次;

第(h-1)层有2个元素,它们最多比较(h-2)次;

第(h-2)层有22个元素,它们最多比较(h-3)次;...;

第1层有2(h-1)个元素,它们最多比较0次

所以,建堆的时间复杂度就是O(n)。

如何在O(n)的时间复杂度内查找一个无序数组中的第K个大元素

** 如何在O(n)的时间复杂度内查找一个无序数组中的第K个大元素?
*  第一次分区查找,我们需要对大小为 n 的数组执行分区操作,需要遍历 n 个元素。

* 第二次分区查找,我们只需要对大小为 n/2 的数组执行分区操作,需要遍历 n/2 个元素。

* 依次类推,分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.

* ……直到区间缩小为 1。
*  如果我们把每次分区遍历的元素个数加起来,就是:n+n/2+n/4+n/8+…+1

  * 这是一个等比数列求和,

* 最后的和等于 2n-1。
所以,上述解决思路的时间复杂度就为 O(n)。
  • n+n/2+n/4+n/8+…+1=2n-1

公众号:offer多多

2021/08/17  阅读:41  主题:橙心

作者介绍

公众号:offer多多