精华内容
下载资源
问答
  • 事后统计法: 通过分析某一个程序算法具体的时间复杂度来度量一个算法的优劣。 时间频度 一个算法花费的时间与算法中语句执行数成正比。哪个算法执行的次数越多,则它花费的时间就多。一个算法中语句执行的次数成为...

    度量一个程序算法执行时间的两种方法

    • 事后统计法: 直白就是把程序跑一边,统计程序从开始到结束花费的时间。缺点在于需要将程序跑一边,如果越到耗时程序的时候效率不高,而且要求计算机的硬件软件的环境一致,保证运行环境相同才有可信度。
    • 事后统计法: 通过分析某一个程序算法具体的时间复杂度来度量一个算法的优劣。

    时间频度

    一个算法花费的时间与算法中语句执行数成正比。哪个算法执行的次数越多,则它花费的时间就多。一个算法中语句执行的次数成为时间频度,记做T(n)。

    例如:计算1-100的总和

    // 方式1
    int total = 0;
    int num = 100;
    for(int i=0;i<=num;i++){
        total = i+total;
    }
    
    // 方式2
    int num = 100;
    int total = (1+num)*num/2
    

    此时方式1中的时间频度为100+1次 记为 T(n)=n+1 n=100因为循环了100次 +1是因为有一个判断

    方式2的时间频度为1 因为只有一条语句 记为 T(n)=1

    时间复杂度

    时间复杂度是度量算法花费时间,算法中的基本操作语句和重复执行次数是问题规模N的某个函数,用T(n)表示,若有有个辅助函数f(n),当n趋近无穷大时,T(n)/f(n)的极限值为一个不等于零的常数,则称f(n)和T(n)是同数量级的函数记为 T(n)=O(f(n)),简称O(n),为一个算法的渐进时间复杂度,简称时间复杂度。

    时间复杂的计算方法

    1. 分析出算法的运行时间频度
    2. 用常数1代替算法中所有加法常数 如 T(n)=2n²+5n+5 ==> T(n)=2²+5n+1
    3. 只保留最高阶项 如 T(n)=2n²+5n+5 ==> T(n)=2n²
    4. 取出最高阶的系数 T(n)=2n²+5n+5 ==> T(n)=n² 则最终时间复杂度为 T(n)=n²记为O(n²)

    常见时间复杂度

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8OhRClVG-1594869812967)(C:\Users\denglw\AppData\Roaming\Typora\typora-user-images\image-20200715103543819.png)]

    1. 常数阶 O(1)

      无论代码执行了多少行,只要没有循环等复杂结构时间复杂度为O(1)

      int i = 1;
      int j = 2;
      i++;
      j++;
      int total = i+j;
      

      ​ 上述代码时间消耗不会随着变量的增长而增长,即i=1或者i=10000都是一样的,无论有多少行,一行或者及万行都可以用O(1)来表示时间复杂度。

    2. 对数阶 O(log2n)

      int i = 1;
      int n = 1024;
      while(i < n){
          i = i*2;
      }
      // 或者
      for(int i=0; i<n; i*=2){
          System.out.println(i);
      }
      

      上述代码中while循环或者for 循环 的执行次数为 以2为底数1024的对数 log2N,当N增大时,时间频度成对数上升,类似于一根长16M的绳子,每次割一半,割到一米需要几次的问题,第一次为8M,第二次为4M,第三次为2M,第四次为1M,则时间频度具体值为4,为log16。则可以记做O(logn)。上述如果把i=i2改成 i=i3 则变成了 log3N 以3为底N的对数了.

    3. 线性阶 O(n)

      int n =100;
      for(int i=0; i<n; i++){
          System.out.println(i);
      }
      

      则表示for循环中需要执行多少次,上述代码是一个线性的,随着N的增加,执行次数就增加N次。如n=100 则执行100次 n=200则执行200次,在坐标轴上是一条直线上升的趋势。记为O(n)

    4. 线性对数阶 O(nlog2n)

      int n =100;
      int m = 1024;
      for(int i=0; i<n; i++){
             while(i < m){
              i = i*2;
          }
      }
      

      简单的理解就是一个对数阶的代码循环N遍则变成了线性对数阶,上述代码中 while循环是一个对数阶 为log1024 记做logN for循环是一个线性阶 n n=100 则他们一起的时间复杂度为O(nlogN)

    5. 平方阶 O(n^2)

      int n = 100;
      int m = 100;
      for (i=0; i < n ; i++){
          for(i=0; i < m ;i++){
              System.out.println(i);
          }
      }
      

      平方阶就是循环套循环,2层循环就是一个n2的平方阶,时间复杂度就是O(n2)

    6. 立方阶 O(n^3)

      立方阶则是3层循环嵌套

    7. k 次方阶 O(n^k)

      k层循环嵌套

    8. 指数阶 O(2^n)

      long function1(int n) {    
          if (n <= 1) {        
              return 1;
          } else {        
              return function1(n - 1) + function1(n - 2);
          }
      }
      

      类似上述从出现递归的时候,T(0) = T(1) = 1,同时 T(n) = T(n - 1) + T(n - 2) + 1,这里的 1 是其中的加法算一次执行。显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列,通过归纳证明法可以证明,当 n >= 1 时 T(n) < (5/3)^n,同时当 n > 4 时 T(n) >= (3/2)^n。所以该方法的时间复杂度可以表示为 O((5/3)^n),简化后为 O(2^n)。

    上述时间复杂度从上到下一次递增,在程序设计过程中需要避免指数阶的时间复杂度。

    空间复杂度

    指程序算法运行过程中对临时占用存储空间如内存的大小,不过从用户体验来是说,用户并不关系后台占用的具体多少内存,只关心多久能给我反馈即执行的速度,所以出现了很多缓存产品,本质上就是用空间换时间的过程。

    展开全文
  • 时间复杂度的计算 1.什么是时间频度时间频度是指算法中最基本的语句执行的次数叫做时间频度; 2.什么是时间复杂度时间复杂度是指当需要处理数据的规模发生变化的时候,计算机计算次数的变化趋势叫做时间...

    时间复杂度的计算

    1.什么是时间频度?

          时间频度是指算法中最基本的语句执行的次数叫做时间频度;
    

    2.什么是时间复杂度?

         时间复杂度是指当需要处理数据的规模发生变化的时候,计算机计算次数的变化趋势叫做时间复杂度;(而且,我么你需要知道时间复杂度越低越好)
         
         那具体是什么意思呢?当时间复杂度为o(n)的时候(n代表需要处理的数据量),说明,计算机需要处理n次,随着n的增长,(语句的执行次数)呈线性增长;
         
         当时间为o(1)时,代表无论需要处理的数据量的多少,计算机的计算次数只有一次,此时为理想的时间复杂度,是所有人梦寐以求的算法;
    
         当时间复杂度为o(n^2)的时候,我们会发现,随着n(处理数据量)的增加,n^2是呈指数式增长的,说明语句的执行次数呈指数增长,众所周知,指数式增长是很快的,所以n越大,o(n^2)的算法的时间频度越高,o(n)相较于o(n^2)就比较好,比如当n为1000时,o(n)=1000,o(n^2)=1000000,由于时间复杂度小的算法好,由此可知,o(n)的算法比o(n^2)的算法要好;
    

    3.时间复杂度如何计算?

         时间复杂度 = 时间频度(去掉低阶的项和常数项,以及最高次项的系数)
         例如  时间频度 f(n)= 2n^2+2 则时间复杂度为O(n^2)
         或    时间频度 f(n)= n^3 + 2n^2 + 3则时间复杂度为O(n^3)
    
    展开全文
  • 时间频度和时间复杂度的计算

    万次阅读 2018-03-25 16:44:28
    (1)时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法...(2)时间复杂度一般情况下,算法中基本操作重复执...
    (1)时间频度
    一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
    (2)时间复杂度
    一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

    在T(n)=4n²-2n+2中,就有f(n)=n²,使得T(n)/f(n)的极限值为4,那么O(f(n)),也就是时间复杂度为O(n²)


    看维基百科的解释,咱先不考虑数学上的概念,在计算机领域,n只能趋近于无穷大,所以,就暂且只考虑这个无穷大的方向。
    T(n)=4n²-2n+2,当n无穷大的时候,后面的“-2n+2”的值对整体T(n)的影响就可以忽略不计。
    用到计算机领域,那么,“-2n+2”的这部分执行时间就可以忽略不计。
    在数学上,T(n)的极限值就是4n²。
    上图中第二段的解释如下:
    当4n²与5n³,这个两个不同级的数,比较的时候,那么前面的系数,4和5,也是无关紧要的,也是可以忽略的。

    展开全文
  • 同一问题可用不同算法解决,而一个算法的质量优劣将影响...1、时间复杂度1.1 时间频度一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)1.2 时间复杂度一般情况下,算法中基本操作重复执行的次数是问题规模...

    同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

    算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是度量算法执行的时间长短;而空间复杂度是度量算法所需存储空间的大小。

    1、时间复杂度

    1.1 时间频度

    一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

    1.2 时间复杂度

    一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

    在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如 T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。

    按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。

    随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

    2、空间复杂度

    一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。

    一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变

    一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法,其空间复杂度为递归所使用的堆栈空间的大小,它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1,这个1表不开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

    对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当=i自求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。

    展开全文
  • 排序算法分类介绍、时间频度时间复杂度1. 排序算法分类介绍2. 算法的时间复杂度3. 算法的空间复杂度 1. 排序算法分类介绍 排序算法的介绍 排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的...
  • 时间频度时间复杂度通常是衡量算法的优劣的,衡量算法的时间严格来讲是很难衡量的,由于不同的机器性能不用环境都会造成不同的执行时间。算法的执行时间语句的执行次数成正比,因此通过计算执行测试来推断执行时间...
  • 算法的时间复杂度和空间复杂度-总结

    万次阅读 多人点赞 2013-09-20 16:01:26
    算法的时间复杂度和空间复杂度 1、时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的...
  • 算法的时间复杂度和空间复杂度一、时间复杂度1.时间频度2.时间复杂度二、空间复杂度1.空间复杂度2.常用的算法的时间复杂度和空间复杂度表格: 一、时间复杂度   通常,对于一个给定的算法,我们要做两项分析:第一...
  • 算法 时间频度 时间复杂度 空间复杂度 算法的时间复杂度 算法的空间复杂度 计算时间复杂度 排序算法的时间复杂度
  • 算法复杂度分为时间复杂度和空间复杂度。 时间复杂度用于度量算法执行的时间长短;而空间复杂度则是用于度量算法所需存储空间的大小。 目录 时间复杂度 1.时间频度 2.计算方法 3.分类 空间复杂度 算法的时间...
  • 时间频度和时间复杂度 (1)时间频度 一个算法执行所耗费的时间.一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。...
  • 这里是用的是输出算法执行前的时间算法执行之后的时间,来查看算法实际花费的时间。 代码: import java.text.SimpleDateFormat; import java.util.Date; //排序前的时间输出 Date date = new Date();...
  • 同一问题可用不同算法解决,而一个算法的质量优劣将影响...1、时间复杂度1.1 时间频度一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)1.2 时间复杂度一般情况下,算法中基本操作重复执行的次数是问题规模...
  • 算法复杂度 时间复杂度:算法所需计算机工作量 空间复杂度:算法所需计算机内存空间 时间复杂度 Time Complexity ...语句频度/时间频度; T(n) = O(f(n)) T(n)f(n)→k(k≠0)\frac {T(n)} {f(n)} \to k...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 651
精华内容 260
关键字:

时间频度和时间复杂度