精华内容
下载资源
问答
  • 时间复杂度怎么算

    2019-11-28 00:05:29
    一、什么是时间复杂度? 一个语句的频度是指该语句在算法中重复执行的次数,算法中所有语句的频度之和是关于问题规模n的函数T(n),时间复杂度就是分析T(n)的数量级来得到的。算法的执行时间与T(n)的数量级成正比,...

    一、什么是时间复杂度?

    一个语句的频度是指该语句在算法中重复执行的次数,算法中所有语句的频度之和是关于问题规模n的函数T(n),时间复杂度就是分析T(n)的数量级来得到的。算法的执行时间与T(n)的数量级成正比,而并不是相等。T(n)的数量级也记为O。

    二、常见的时间复杂度排序

    O(1) < O(\log {_{2}}n)<O(n)<O(n\log {_{2}}n)<O(n^{2})<O(n^{3})<O(2^{n})<O(n!)<O(n^{n})

    三、时间复杂度计算举例

    首先看O(1)时间复杂度的例子:

    int i = 0;
    int j = 1;
    printf("%d",i+j);

    上述代码为什么是常数级,我用我自己认为比较好理解的方法来理解,第一部分已经说到,语句的频度是指重复执行的次数,所以这里就是常数级。

    再看一个O(\log {_{2}}n)的例子:

    1   void fun(int n){
    2     int i = 1;
    3     while(i<=n)
    4        i = i*2;
    5   }

    计算这个算法的时间复杂度,首先找到重复执行的基本语句,也就是第四行的语句。这个执行的次数明显和n有关。我们首先设要重复执行x次才完成,那么则有 2^{x}=n,解出x=\log {_{2}}n。这就是本算法的时间复杂度。

    再看一个O(n)时间复杂度的例子:

    1    int fact(int n){
    2        if(n<=1) return 1;
    3        return n*fact(n-1);
    4    }

    找到重复执行的语句,即3行,明显要一直重复n遍才能结束递归过程。所有时间复杂度为O(n)。

    或者一个更简便的for循环的例子也是O(n)

    for(int i = 0; i<n;i++){
        printf("%d",i)
    }

    O(n\log {_{2}}n)的时间复杂度显而易见是O(n)乘以O(\log {_{2}}n),如下面的代码。

    while(i<=n){
        for(int j=0;j<n;j++)
            printf("%d",j);
        i*=2;
    }

    以此类推,O(n^{2})、O(n^{3})分别是O(n)*O(n)或者O(n)*O(n)*O(n)

    时间不早了,时间复杂度简单的举例先介绍到这里,下一篇文章再计算其他较为复杂的时间复杂度例子。

    展开全文
  • 时间复杂度怎么算详解 我们假设计算机运行一行基础代码需要执行一次运算。 int aFunc(void) { printf("Hello, World!\n"); // 需要执行 1 次 return 0; // 需要执行 1 次 } 那么上面这个方法需要执行 2 次运算 ...

    时间复杂度怎么算详解

    我们假设计算机运行一行基础代码需要执行一次运算。

    int aFunc(void) {
        printf("Hello, World!\n");      //  需要执行 1 次
        return 0;       // 需要执行 1 次
    }
    

    那么上面这个方法需要执行 2 次运算

    int aFunc(int n) {
        for(int i = 0; i<n; i++) {         // 需要执行 (n + 1) 次
            printf("Hello, World!\n");      // 需要执行 n 次
        }
        return 0;       // 需要执行 1 次
    }
    
    

    这个方法需要 (n + 1 + n + 1) = 2n + 2 次运算。

    我们把 算法需要执行的运算次数 用 输入大小n 的函数 表示,即 T(n) 。
    此时为了 估算算法需要的运行时间 和 简化算法分析,我们引入时间复杂度的概念。

    定义:存在常数 c 和函数 f(N),使得当 N >= c 时 T(N) <= f(N),表示为 T(n) = O(f(n)) 。
    如图:
    在这里插入图片描述
    当 N >= 2 的时候,f(n) = n^2 总是大于 T(n) = n + 2 的,于是我们说 f(n) 的增长速度是大于或者等于 T(n) 的,也说 f(n) 是 T(n) 的上界,可以表示为 T(n) = O(f(n))。

    因为f(n) 的增长速度是大于或者等于 T(n) 的,即T(n) = O(f(n)),所以我们可以用 f(n) 的增长速度来度量 T(n) 的增长速度,所以我们说这个算法的时间复杂度是 O(f(n))。

    算法的时间复杂度,用来度量算法的运行时间,记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大,算法执行需要的时间的增长速度可以用 f(n) 来描述。

    显然如果 T(n) = n^2,那么 T(n) = O(n^2),T(n) = O(n^3),T(n) = O(n^4) 都是成立的,但是因为第一个 f(n) 的增长速度与 T(n) 是最接近的,所以第一个是最好的选择,所以我们说这个算法的复杂度是 O(n^2) 。
    具体步骤
    ⑴ 找出算法中的基本语句;

    算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。

    ⑵ 计算基本语句的执行次数的数量级;

    只需保留f(n)中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。

    ⑶ 用大Ο记号表示算法的时间性能。

    将基本语句执行次数的数量级放入大Ο记号中。

    举例

    1. 对于一个循环,假设循环体的时间复杂度为 O(n),循环次数为 m,则这个循环的时间复杂度为 O(n×m)。
    void aFunc(int n) {
        for(int i = 0; i < n; i++) {         // 循环次数为 n
            printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
        }
    }
    
    

    此时时间复杂度为 O(n × 1),即 O(n)。

    2.对于多个循环,假设循环体的时间复杂度为 O(n),各个循环的循环次数分别是a, b, c…,则这个循环的时间复杂度为O(n×a×b×c…)。分析的时候应该由里向外分析这些循环。

    void aFunc(int n) {
        for(int i = 0; i < n; i++) {         // 循环次数为 n
            for(int j = 0; j < n; j++) {       // 循环次数为 n
                printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
            }
        }
    }
    
    

    此时时间复杂度为 O(n × n × 1),即 O(n^2)。

    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)
        for(int j = 0; j < n; j++) {
            printf("Hello, World!\n");
        }
    }
    此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。
    
    1. 对于条件判断语句,总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。
    void aFunc(int n) {
        if (n >= 0) {
            // 第一条路径时间复杂度为 O(n^2)
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    printf("输入数据大于等于零\n");
                }
            }
        } else {
            // 第二条路径时间复杂度为 O(n)
            for(int j = 0; j < n; j++) {
                printf("输入数据小于零\n");
            }
        }
    }
    
    

    此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。

    时间复杂度分析的基本策略是:从内向外分析,从最深层开始分析。如果遇到函数调用,要深入函数进行分析。

    练习
    1.

    void aFunc(int n) {
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                printf("Hello World\n");
            }
        }
    }
    
    

    当 i = 0 时,内循环执行 n 次运算,当 i = 1 时,内循环执行 n - 1 次运算……当 i = n - 1 时,内循环执行 1 次运算。
    所以,执行次数 T(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。
    根据上文说的 大O推导法 可以知道,此时时间复杂度为 O(n^2)。

    void aFunc(int n) {
        for (int i = 2; i < n; i++) {
            i *= 2;
            printf("%i\n", i);
        }
    }
    
    

    假设循环次数为 t,则循环条件满足 2^t < n。
    可以得出,执行次数t = log(2)(n),即 T(n) = log(2)(n),可见时间复杂度为 O(log(2)(n)),即 O(log n)。

    long aFunc(int n) {
        if (n <= 1) {
            return 1;
        } else {
            return aFunc(n - 1) + aFunc(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)。

    时间复杂度分析的基本策略是:从内向外分析,从最深层开始分析。如果遇到函数调用,要深入函数进行分析。

    展开全文
  • 时间复杂度怎么算

    多人点赞 2020-12-31 13:08:24
    时间复杂度计算时间复杂度计算案例大O表示法 时间复杂度:估算程序指令执行的次数 时间复杂度计算案例 注意:为了方便,省略了方法的修饰,只保留了方法名 method1(){ System.out.println("祝你看了这篇文章"); //...
    image-20201231130906583
    

    时间复杂度:估算程序指令执行的次数

    时间复杂度计算案例

    注意:为了方便,省略了方法的修饰,只保留了方法名

    method1(){
    	System.out.println("祝你看了这篇文章"); //执行1次
    	System.out.println("诸事顺利"); //执行1次
    	System.out.println("万事如意"); //执行1次
    }
    // 1+1+1 = 3
    

    method2(){
    	for(int i=0;i<5;i++){ //i=0 执行1次;i<5 判断5+1次,等于5时判断后退出;i++ 执行5次
    		System.out.println("点赞发财!"); //执行5次
    	}
    }  //1+(5+1)+5+5 = 17
    

    method3(int n){
    	for(int i=0;i<n;i++){ //i=0 执行1次;i<n 执行n+1次;i++ 执行n次
    		System.out.println("点赞好运!"); //执行n次,你会有n次好运哦
    	}
    } //1+(n+1)+n+n = 3n+2
    

    method4(int n){
    	for(int i=0;i<n;i++){  //i=0 执行1次;i<n 执行n+1次;i++ 执行n次
    		//整个内层循环 执行n次
    		for(int j=0;j<n;j++){ //j=0 执行1次;j<n 执行n+1次;j++ 执行n次
    			System.out.println("你很帅"); //执行n次
    		}
    	}} //外层2n+2; 复杂度:2n+2+n*(3n+2) = 3n^2+4n+2
    

    method5(int n){
    	for(int i=0;i<n;i++){ //i=0 执行1次;i<n 执行n+1次;i++ 执行n次
    		// 整个内层循环执行n次
    		for(int j=0;j<15;j++){ //j=0 执行1次;j<15 执行15+1次;j++ 执行15次
    			System.out.println("高山流水"); //执行15次
    		}
    	} } // 复杂度:2n+2+n*(47) = 49n+2
    

    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):判断语句执行次数
    */
    

    method7(int n){
    	while((n=n/5)>0){
    		System.out.println("欲练神功");
    	}
    } // 由method6可知,复杂度:log5(n)+(log5(n)+1) = 2log5(n)+1
    //   log5(n):循环体内执行次数, (log5(n)+1):判断语句执行次数 
    

    method8(int n){
    	for(int i=1;i<n;i=i*2){
    		for(int j=0;j<n;j++){ //j=0 1次,j<n n+1次,j++ n次
    			System.out.println("你懂的");// n次
    		}
    	}}
    	/*
    	i=1, i=1*2=2, i=1*2*2=4, i=1*2*2*2=8 ;  所以i<n执行次数=log2(n)+1; (多1是判断一次不满足条件退出循环时)
    	如果n=8, i<n 执行判断4次 log2(8)+1; 内层整个循环执行log2(8)=3次
    	
    	复杂度:1+(log2(n)+1)+log2(n)+[log2(n)*(1+(n+1)+n)] = 2nlog2(n)+4log2(n)+2
    	左到右:1:i=1执行次数; log2(n)+1:i<n执行次数; log2(n):i=i*2执行次数
    	[log2(n)*(1+(n+1)+n)]:log2(n):整个内层循环执行次数;(1+(n+1)+n):内层循环的执行次数
    	*/
    

    method9(int n){
    	for(int i=0;i<n;i++){ // i=0 执行1次;i<n 执行n+1次;i++ 执行n次
    		for(int j=i;j<n;j++){
    			System.out.println("谢谢点赞");
    		}
    	}}
    	/*
    	 i=0,内部执行n次;i=1,内部执行n-1; i=2,内部执行n-2;…… i=n-1,内部循环执行1次。等差数列
    	 =n*(n+1)/2 = (1/2)n^2+(1/2)n; 
    	 所以内部循环除了j<n需要多执行判断一次外,其他都是执行(1/2)n^2+(1/2)n次
    	 时间复杂度:2n+2+4*((1/2)n^2+(1/2)n)+1 
    	 4*((1/2)n^2+(1/2)n)+1 : 内层循环执行次数
    	 int j=i; j<n; j++; System.out.println("谢谢点赞"); 
    	 这4条除了 j<n 执行了 (1/2)n^2+(1/2)n +1 
    	 其他3个都是 (1/2)n^2+(1/2)n
    	*/
    

    大O表示法

    上面的时间复杂度的表示还是较复杂,我们一般都使用大O表示法来简化表示时间复杂度。

    1、复杂度为常数,如23,9999,等等 都表示为O(1)

    2、复杂度包含n时,省略系数与常数项,只取n的最高阶项

    ​ 如:2n+45 为 O(n) ; 4n^3 + 6n^2+n 为O(n^3)

    3、复杂度为对数时:如log5(n)、log2(n) 等等 都表示为 O(logn)

    4、省略低阶,只取高阶 (即取最大的)

    ​ 如:logn+nlogn 表示为O(nlogn)

    复杂度的大小

    O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

    复杂度越小,则说明你的代码越好

    那么上面的 method1~method9 用大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)
    
    展开全文
  • ⑴ 找出算法中的基本语句;  算法中执行次数最多的那条语句就是基本语句,通常是最内层... ⑶ 用大Ο记号表示算法的时间性能。  将基本语句执行次数的数量级放入大Ο记号中。  如果算法中包含嵌套的...
       ⑴ 找出算法中的基本语句;
     
      算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
     
      ⑵ 计算基本语句的执行次数的数量级;
     
      只需保留f(n)中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。
     
      ⑶ 用大Ο记号表示算法的时间性能。
     
      将基本语句执行次数的数量级放入大Ο记号中。
     
      如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如:
     
      for (i=1; i<=n; i++)
      x++;
     
      for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
          x++;
     
      第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n²),则整个算法的时间复杂度为Ο(n+n²)=Ο(n²)。
      注、加法原则:T(n)=O(f(n))+O(g(n))=O(max(fn,gn))
     
      常见的算法时间复杂度由小到大依次为:
     
      Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n²)<Ο(n³)<…<Ο(2^n)<Ο(n!)<O(n^n)
     
    Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P类问题,而把后者称为NP问题。
     
     
     
    对于一个循环,假设循环体的时间复杂度为 O(n),循环次数为 m,则这个循环的时间复杂度为 O(n×m)。
     
    void aFunc(int n) {
    
      for(int i = 0; i < n; i++) { // 循环次数为 n
    
      printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
    
      }
    }

     

    此时时间复杂度为 O(n × 1),即 O(n)。

    对于多个循环,假设循环体的时间复杂度为 O(n),各个循环的循环次数分别是a, b, c...,则这个循环的时间复杂度为 O(n×a×b×c...)。分析的时候应该由里向外分析这些循环。

    void aFunc(int n) {
        for(int i = 0; i < n; i++) { // 循环次数为 n
            for(int j = 0; j < n; j++) { // 循环次数为 n
                printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
            }
        }
    }                

     

    此时时间复杂度为 O(n × n × 1),即 O(n^2)。

     

    对于顺序执行的语句或者算法,总的时间复杂度等于其中最大的时间复杂度。

    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)
    for(int j = 0; j < n; j++) {
      printf("Hello, World!\n");
    }
    }

     

    此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。

    对于条件判断语句,总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。

    void aFunc(int n) {
    if (n >= 0) {
    // 第一条路径时间复杂度为 O(n^2)
    for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
    printf("输入数据大于等于零\n");
    }
    }
    } else {
    // 第二条路径时间复杂度为 O(n)
    for(int j = 0; j < n; j++) {
    printf("输入数据小于零\n");
    }
    }
    }

     

    此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。

    时间复杂度分析的基本策略是:从内向外分析,从最深层开始分析。如果遇到函数调用,要深入函数进行分析。

    转载于:https://www.cnblogs.com/wonker/p/11236988.html

    展开全文
  • ![图片](https://img-ask.csdn.net/upload/201709/18/1505732081_208487.png)
  • *** for(int i=0;i;i++){ dfn[i] = 0; low[i] = 0; vis[i] = false; first[i] = -1; first2[i] = -1;///反向建边 color[i] = 0;...弱弱问一句,什么那个语句时间复杂度是多少???
  • 对于k的话之前是k,现在是k 这个乍一看还看不出来时间复杂度是多少,所以我们需要进行推导一下,怎么推导呐,具体的推导过程还不懂,那你得好好看看《烦不烦,别再问我时间复杂度了:这次不色,女孩子进来吧 - 第...
  • 递归的时间复杂度怎么算? 一般情况下,可以用以下公式: T(N)=aT(N/b)+O(N^d); 其中,T是样本,N的样本量。 b代表这个样本被分为了几部分(上面的算法被分为两部分(L+R)/2,所以b=2),a代表运行了多少次(上面的...
  • 计算机的资源,最重要的是时间和空间(即存储器)资源。因而,算法的复杂性有时间复杂性和空间复杂性之分。 对于任意给定的问题,设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标;另一方面,当...
  • void sort(int a[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) for (int i = gap; i < n; ++i) for (int j = i - gap; j >= 0 && a[j + gap] <...//需要计算过程
  • 感觉有时候评价一个算法的时间复杂度挺难的,特别是递归的时候,大家一般怎么看啊?
  • 递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间 对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。 a = 0 b =...
  • 时间复杂度和空间复杂度的算法与辨析举例时间复杂度基础时间复杂度渐进时间复杂度空间复杂度 时间复杂度 即执行算法的时间成本 基础时间复杂度 基本操作执行次数:一个循环内的操作次数 时间复杂度=循环次数*每步...
  • 【转载】时间复杂度到底怎么算 时间复杂度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 262
精华内容 104
关键字:

时间复杂度怎么算