精华内容
下载资源
问答
  • 《数据结构系列_计算时间复杂度

    万次阅读 2019-05-09 16:08:55
    1.前言 本来接下来想更新线性表的,结果我的一个小伙伴面试的时候碰到了这个题目,就打算先梳理科普一下这块的内容。...2.计算时间复杂度是做什么的?有什么 答:首先先了解时间复杂度是什么,时间复杂度就是 ...

    1.前言

    本来接下来想更新线性表的,结果我的一个小伙伴面试的时候碰到了这个题目,就打算先梳理科普一下这块的内容。

    2.计算时间复杂度是做什么的?有什么用

    时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的。

    答:官方的解释,因为受硬件环境和输入规模的影响,代码的绝对执行时间是无法估计的,但是可以估算代码的基本执行次数。所以简单理解,时间复杂度就是其实简单来讲,就是用来计算算法基本操作的执行次数,描述该算法运行的时间的。衡量代码的好坏重要的2个指标就是运行时间和占用空间。

    3.计算代码的执行次数

    明白了时间复杂度是个什么意思之后,先看两个列子。

    No1.

      public static void main(String[] args) {
    
            System.out.println("Hello world"); // 执行1次
            System.out.println("Hello 数据结构"); // 执行1次
      }
    

    那么上面这个方法需要执行 1+1=2 次运算。运算时间记作T(n) = 1

    No2.

      for (int i = 0; i < n; i++) {// 执行n + 1 次
    
          System.out.println("Hello world"); // 执行n次
          System.out.println("Hello 数据结构"); // 执行n次
      }
    

    一共执行了n +1 +n +n = 3n+1次,运算时间记作T(n) = 3n+1

    时间复杂度常用大O符号表述,时间的增长速度可以用 f(n) 来描述记作: T(n) = O(f(n))。随着 输入大小n 的增大,算法执行时间的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效率越高。


    4.推导时间复杂度的原则

    1.我们晓得:常数项对函数的时间增长速度的影响并不大,所以当T(n)=c(常数)时,我们说这个时间复杂度为O(1),当T(n)不等于一个常数时,我们是可以把常数项忽略不计

    比如当T(n) = 8 时间复杂度记作O(1),当T(n)=n+8, 忽略常数项,时间复杂度记为O(n)

    2.我们晓得:对于一个函数而言,它的阶数对它的变化影响是最大的,所以通常在计算时间复杂度的时候,我们只会保留最高项的阶数,忽略掉与它相乘的系数。

    比如当T(n) = 8n²+3,忽略常数项,忽略最高项的系数,时间复杂度记作O(n²)

    3.我们晓得:一个函数中,高次项对函数的变化影响是最大的,所以我们在计算时间复杂度的时候,通常忽略低次项,只保留最高项

    比如当T(n) = 4n³+8n²+3,忽略常数项,忽略最高项的系数,只保留最高项,时间复杂度记作O(n³)

    这个又叫做大O推导法
    总结就是

    5.练一练

    1.计算下面的时间复杂度

       for (int i = 0; i < n; i++) {// 执行n + 1 次
    
                System.out.println("Hello world"); // 执行n次
       }
    

    时间复杂度为:T(n) = 2n+1,根据上面的规则,最后:T(n) = O(n)

    2.计算下面的时间复杂度

    for (int i = 0; i < n; i++) {// 执行n + 1 次
        for (int m = 0; m < n; m++) {// 执行n * n 次
    
            System.out.println("Hello world"); // 循环体时间复杂度为O(1)
        }
    }
    

    时间复杂度为T(n) = n×n×O(1) = O(n²)

    3.计算下面的时间复杂度

     for (int k = 0; k < n; k++) {// 执行 n + 1 次
    
         System.out.println("Hello bmw"); // 循环体O(1)
     }
    
     for (int i = 0; i < n; i++) {// 执行n + 1 次
         for (int m = 0; m < n; m++) {// 执行n * n 次
    
             System.out.println("Hello Audi"); // 循环体O(1)
          }
     }
    

    这个时间复杂度为多少尼?
    第一个循环的时间复杂度为O(n),第二个双层循环的时间复杂度为O(n²),根据我们只保留最高项,这个函数的时间复杂度为T(n) = O(n²)。


    4.计算下列时间复杂度

      if(true){
          for (int k = 0; k < n; k++) {// 执行 n + 1次
    
              System.out.println("Hello bmw"); // 循环体O(1)
          }
      }else {
          for (int i = 0; i < n; i++) {// 执行n + 1 次
              for (int m = 0; m < n; m++) {// 执行n * n 次
    
                   System.out.println("Hello Audi"); // 循环体O(1)
               }
          }
      }
    

    来算一下时间复杂度是多少?
    这个的时间复杂度为T(n) = O(n), 第一个for循环的时间复杂性为T(n)=O(n) 第二个时间复杂度为T(n) = O(n²),对于条件判断语句,总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。但是if是true,else是不会执行的。


    5.计算下列时间复杂度

    for(int i=2; i< n; i++){
        i * =2;
        System.out.println("i="+i);
    }
    

    先计算循环次数,
    假如设定循环了x次,那么循环的条件就是2^x < n, 那么x = log(2)(n),所以T(n) = O(log(2)(n)) 即T(n) = O(log n)

    6.思考题

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

    来计算一下这个,知道的小伙伴可以底下留言。答案在下期博客

    展开全文
  • 今天我们来谈一下如何计算时间复杂度。 时间复杂度概念:(百度版) 同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。 计算机科学中,算法...

    今天我们来谈一下如何计算时间复杂度。

    时间复杂度概念:(百度版)

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

    计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。

    注意:本文承接上一篇《数据结构与算法-函数的渐近增长》,想详细了解渐近增长,请点击:数据结构与算法-函数的渐近增长


    现在先上代码,请大家详细阅读注释,因为整个计算过程都已经在注释里面体现。


    /**
     * 计算时间复杂度
     * 
     * @author ray
     * 
     */
    public class Test {
    
    	private void test1(int n) {
    		System.out.println(n);// 操作=1
    	}
    
    	private void test2(int n) {
    		int a = 0;
    		for (int i = 0; i < n; i++) {// 操作=n
    			a++;// 操作=1
    		}
    		// 总操作=n*1=n
    		// 时间复杂度=O(1)
    	}
    
    	private void test3(int n) {
    		int a = 0;
    		for (int i = 0; i < n; i++) {// 操作=n
    			for (int j = 0; j < n; j++) {// 操作=n
    				a++;// 操作=1
    			}
    		}
    		// 总操作=n*n*1=n^2
    		// 时间复杂度=O(n^2)
    	}
    
    	private void test4(int n) {
    		int a = 0;
    		for (int i = 0; i < n; i++) {
    			for (int j = i; j < n; j++) {// 操作=n,n-1,n-2,n-3......1=(n+1)n/2
    				a++;// 操作=1
    			}
    		}
    		// 总操作=(n+1)n/2=n^2/2+n/2
    		// 由于时间复杂度是一个抽象的概念,当n的规模达到一定程度的时候,时间复杂度只取最高次幂,而且忽略其他次要项和系数
    		// 时间复杂度=O(n^2)
    	}
    
    	private void test5(int n) {
    		int a = 0;
    		for (int i = 0; i < n; i++) {
    			for (int j = i; j < n; j++) {// 操作=n,n-1,n-2,n-3......1=(n+1)n/2
    				a++;// 操作=1
    				System.out.println(a);// 操作=1
    				// for循环内总操作=2
    			}
    		}
    		// 总操作=(n+1)n/2*2=n^2+n
    		// 由于时间复杂度是一个抽象的概念,当n的规模达到一定程度的时候,时间复杂度只取最高次幂,而且忽略其他次要项和系数
    		// 时间复杂度=O(n^2)
    	}
    
    	private void test6(int n) {
    		int a = 0;
    		for (int i = 0; i < n; i++) {
    			for (int j = i; j < n; j++) {// 操作=n,n-1,n-2,n-3......1=(n+1)n/2
    				a++;// 操作=1
    				System.out.println(a);// 操作=1
    				System.out.println(i);// 操作=1
    				// for循环内总操作=3
    			}
    		}
    		// 总操作=(n+1)n/2*3=n^2*3/2+n*3/2
    		// 由于时间复杂度是一个抽象的概念,当n的规模达到一定程度的时候,时间复杂度只取最高次幂,而且忽略其他次要项和系数
    		// 时间复杂度=O(n^2)
    	}
    
    	private void test7(int n) {
    		int a = 0;
    		int b = 0;
    		for (int i = 0; i < n; i++) {// 操作=n
    			for (int j = 0; j < n; j++) {// 操作=n
    				a++;// 操作=1
    				System.out.println(a);// 操作=1
    				// for循环内总操作=2
    				for (int k = 0; k < n; k++) {// 操作=n
    					b++;// 操作=1
    					// for循环内总操作=1
    				}
    			}
    		}
    		// 总操作==n^3+2n^2
    		// 由于时间复杂度是一个抽象的概念,当n的规模达到一定程度的时候,时间复杂度只取最高次幂,而且忽略其他次要项和系数
    		// 时间复杂度=O(n^3)
    	}
    
    	public static void main(String[] args) {
    		int n = 10;
    		Test t = new Test();
    		t.test1(n);
    		t.test2(n);
    		t.test3(n);
    		t.test4(n);
    		t.test5(n);
    		t.test6(n);
    		t.test7(n);
    	}
    }
    



    展开全文
  • 时间复杂度计算

    2015-07-24 15:31:48
    这是一个关于代表算法输入值的字符长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。 求解算法的时间复杂度的具体步骤是:  ⑴ 找出算法中的基本语句;  算法中执行次数最多的那...

             算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。

    求解算法的时间复杂度的具体步骤是:

      ⑴ 找出算法中的基本语句;

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

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

      只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。

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

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

    如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如:

      for (i=1; i<=n; i++)
      x++;

      for (i=1; i<=n; i++)
      for (j=1; j<=n; j++)
      x++;

      第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

      常见的算法时间复杂度由小到大依次为:

      Ο(1)<Ο(log2 n)<Ο(n)<Ο(nlog2 n)<Ο(n^2)<Ο(n^3)<…<Ο(2^n)<Ο(n!)

    Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P类问题,而把后者称为NP问题。

    这只能基本的计算时间复杂度,具体的运行还会与硬件有关。

    上面的这部分内容是比较可靠的,理解的时候,可以参看着下面的这部分内容。

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

    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;                             / * T3(n) = O(1) */

    ④ 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(1+n))=O(n*n*n)即为整个算法的时间复杂度

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


    例题:

    Which of the choices below correctly describes the amount of time used by the  following code?(下面哪个选项正确地描述了代码运行的调度次数?)


    解答:x=x+1;是循环最内侧的代码,其时间复杂度最高,所以只求这句代码的复杂度即可

    从内到外看,k循环从1==20开始每次变成原来的2倍,一直到大于n-1,所以循环体运行次数为|log(n)|,时间复杂度为O(log(n))(计算机中log默认底数是2);

    j循环从1开始每次递增n/2,一直到n-1,第一次递增之后j变成(n+2)/2,第二次递增j则是n+1,所以应该是循环了2次,但是时间复杂度还是O(1),因为常数次数的时间复杂度都是O(1)的;

    i循环从1开始,每次增1一直到n-1,所以循环体运行n-1次,时间复杂度O(n)。

    最后相乘得到总的时间复杂度为O(n*1*log(n))=O(n*log(n)),这里要强调一下:时间复杂度都不带常数项或者常数系数,所以不存在所谓O(2n)这样的时间复杂度。

    答案:D



    展开全文
  • 题目:给定一个字符,请你找出其中不含有重复字符的最长子串 的长度。 示例一: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例二: 输入: "bbbbb" 输出: 1 解释: ...

    题目:给定一个字符串,请你找出其中不含有重复字符的最长子串 的长度。时间复杂度O(n)

    示例一

    输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
    

    示例二:

    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
    

    示例三:

    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
    

    思路:

    • 本题用“滑动窗口”方法解答。

    • 第一步:创建一个容器(注意:创建容器要调用头文件<vector>)存储无重复字符的长子串,并创建一个临时变量n储存容器的长度,创建一个变量MaxSize储存无重复字符的最长子串的长度。

    	#include<vector>
    	vector<char> test;	//创建一个容器
    	int MaxSize(0), n(1);
    
    • 第二步:容器每新增加一个字符,建立一个for循环,判断该字符在容器中是否重复,若不重复,临时变量n++,若重复,则用容器删除方法erase()删除从容器的第一个元素到该重复元素。并且n的值要减去删除子串的长度,被删除字串的长度刚好该重复元素的下标值。
    • 例如:容器中若储存的元素为"abcdefg",此时n的值为7,新增元素为c,则将容器中的"abc"删除,剩下"defgc";因为原容器中c的下标为2,此时n的值要减去原容器重复元素的下标,即n = n-2;
    	test.push_back(s[i]);
    		n = test.size();
    		for (int j = 0; j < n-1; j++)
    		{
    			if (test[j] == s[i])
    			{
    				test.erase(test.begin(), test.begin() + (j + 1));
    				break;
    			}
    		}
    
    • 第三步:将n的值与MaxSzie作比较,然后循环将字符串中的字符都进入容器中比较一遍
    n = test.size();
    MaxSize = MaxSize > n ? MaxSize : n;
    

    完整代码如下:

    #include<iostream>
    #include<vector>;
    using namespace std;
    int main()
    {
    	string s = "abcdefghib";
    	vector<char> test;
    	int MaxSize(0), n(1);
    	for (int i = 0; i < s.length(); i++)
    	{
    		test.push_back(s[i]);
    		n = test.size();
    		for (int j = 0; j < n-1; j++)
    		{
    			if (test[j] == s[i])
    			{
    				test.erase(test.begin(), test.begin() + (j + 1));
    				break;
    			}
    		}
    		n = test.size();
    		MaxSize = max(MaxSize, n);
    	}
    	cout << MaxSize << endl;
    }
    

    运行结果:

    9
    

    欢迎指出错误批评改正。如有更好的办法,欢迎在评论区留言讨论~~

    展开全文
  • 时间复杂度计算

    2020-05-28 17:55:49
    使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。 时间复杂度的表示方法 其实就是算法(代码)的执行效率,算法代码的执行时间。我们来看下面一个简单的代码: int sumFunc(int n...
  • 时间复杂度:O(2n) = O(n)O(2n)=O(n),在最糟糕的情况下,每个字符将被 startIdx 和 endIdx 访问两次 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2: 输入:...
  • 时间复杂度

    2019-05-21 14:25:10
    O(n)不是算法,它是一个函数,是一个表征算法时间复杂度的一...使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。 扩展资料: 算法复杂度分为时间复杂度和空间复杂度。 其作用: ...
  • 算法时间复杂度计算Just like writing your very first for loop, understanding time complexity is an integral milestone to learning how to write efficient complex programs. Think of it as having a ...
  • 如果你还在发愁究竟怎么计算时间复杂度和空间复杂度,那你是来对地方了! 名词解释: 在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入...
  • 时间复杂度和空间复杂度

    多人点赞 2021-08-29 20:40:29
    1.时间复杂度的概念和计算方法 2.几个简单算法的时间复杂度 1.循环嵌套 2.二分查找 3.冒泡排序 2.空间复杂度 1.空间复杂度的概念和计算方法 2.几个简单算法的时间复杂度 1.未定数组 2.递归函数 1.时间...
  • 一、确定性模型的计算复杂性关系、 二、证明 "多个带子图灵机时间复杂度
  • 关于时间复杂度

    2019-09-26 10:58:28
    时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。(算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此...
  • 使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。 分析一个算法的时间复杂度步骤: 找到执行次数最多的语句 语句执行语句的数量级 O表示结果 万能方法 其次: 常数1取代...
  • 时间复杂度与空间复杂度

    千次阅读 2018-05-23 14:18:58
    算法的时间复杂度描述了一个程序该算法的运行时间,是一个关于代表算法输入值的字符长度的函数,相当于计算一个程序总共执行了多少次,这个计算次数的表达式,就是该程序的时间复杂。大O符号表示。不包含函数...
  • 时间复杂度:O(n) * * 这里需要分为两步,第一步是获取,以每个位置开头最小和的长度。第二步,从0到N逐一判断刚才最小长度是否可以合并在一起达到小于等于k的效果。 * * 第一步: 获取以每个位置开头的最小...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,519
精华内容 27,007
关键字:

如何用串长度计算时间复杂度