精华内容
下载资源
问答
  • 算法复杂度

    2019-07-24 11:09:03
    什么是算法复杂度?2.什么是空间复杂度?3.什么是时间复杂度?4.如何计算一个算法的时间复杂度?1.算法复杂度1.1.什么是算法复杂度?算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是指执行这个算法所...

    问题导读

    1.什么是算法复杂度?
    2.什么是空间复杂度?
    3.什么是时间复杂度?
    4.如何计算一个算法的时间复杂度?



    1.算法复杂度
    1.1.什么是算法复杂度?
    算法复杂度分为时间复杂度和空间复杂度。其作用:
     

    • 时间复杂度是指执行这个算法所需要的计算工作量;
    • 而空间复杂度是指执行这个算法所需要的内存空间;



    时间和空间都是计算机资源的重要体现,而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少;

    1.2.什么是空间复杂度?
    一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。

    固定部分:这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。
    可变空间:这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。

    1.3.什么是时间复杂度?
    关于时间频度:
    一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n);

    在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。记为O(…),也称为大O表示法;

    另外,时间频度不同,但时间复杂度可能相同。如:T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2) //注意这里n2是n方的意思

    时间复杂度去估算算法优劣的时候注重的是算法的潜力,也就是在数据规模有压力的情况之下(最坏情况)算法的执行频度,什么意思呢?比如2个算法,在只有100条数据的时候,算法a比算法b快,但是在有10000条数据的时候算法b比算法a快,这时候我们认为算法b的时间复杂对更优;

    1.4.时间复杂度与空间复杂度的取舍问题
    查阅了诸多资料,最后还是感觉这段解释比较靠谱,下面摘出这篇博客的观点:
    https://blog.csdn.net/qiumengchen12/article/details/45697405

    就目前来说,除了在一些特殊情况下,我们都是更加注重时间复杂度,而不是空间复杂度。注意,这里我们强调了,除了一些特殊情况外,有些特殊情况下,空间复杂度可能会更加重要。

    那么,究竟什么时候应该着重考虑时间复杂度,什么时候应该着重考虑空间复杂度呢?我们来看一个例子:

    设想现在需要由你来完成一个程序设计,程序要求是这样的:要求输入年份,返回该年份是否是闰年。

    一提到这个问题,我想如果你学习过任何一门语言,你可能都做过类似的题目。你可能思路已经非常清晰了,满百除四百,不满除以4。

    额,先不要急。我们来看看还能不能进一步提高性能,降低时间复杂度。也就是用空间复杂度来换取时间复杂度。比如,如果使用我们程序的用户,只会查看当前年份未来几年和过去几年的日历的话,我们完全可以使用一个比如:2100个元素的数组,每个元素为0或1,分别表示平年和闰年。这样当用户查询的时候,就不需要再进行复杂的逻辑判断,而只需要取出对应下标位置的元素即可。
    反过来,如果我们的用户经常查询跨度上万年的日历信息(万年历),那么,我们肯定不能使用上面牺牲空间复杂度来换取时间复杂度的方案解决。因为如此巨大的空间消耗是我们损失不起的。

    而,编程的精髓和美,并不在于一方的退让和妥协。而是在于如何在二者之间取一个平衡点,完成华丽变身。那么,对于我们这种程序应该如何权衡呢?

    我想到的一种方案是:将与当前年份相近的几年存为固定数据,查询时只需要读取即可。而对于那些和当前年份相距较远的年份的数据,在用户请求查询时动态生成。

    这样,既能在损失可接受空间的情况下,大幅度提高性能,又能保证空间的损失不至于太大而无法接受。我想当用户查询据今较远的数据时,有一些时间上的等待,也是可以接受的。

    总结下这一段的核心思想:
    不能简单的说时间复杂度就比空间复杂度重要,在特定场景下空间复杂度反而比时间复杂度重要,在程序中我们需要综合考虑让时间和空间的消耗达到一个平衡点,从上面平闰年计算的例子来看,我们可以缓存前后几年间的平润年,因为内存开销在可控范围内,至少是在现有条件下能够体验到的可接受范围,所以这几年的数据我们可以用增大空间消耗来减少时间的消耗,如果说要将一万年的所有平闰年数据都存上,那么即便是内存能撑得住也是得不偿失的,所以这时候我们用增大时间开销(网络请求,动态加载)去交换减少空间的开销(省去了万级数据的存储空间); 所以综上,这就是个综合考量的问题; 

    另外我总是在想一个牛角尖问题,时间和空间都是算法复杂度的考量标准,但是现在说算法好坏好像更多的人关注的时间复杂度,空间复杂度却不去考虑,或者说空间复杂度不是那么重要?这是为什么呢?

    上面也分析了,时间换空间或空间换时间都是根据现实情况来分析,而目前的现实情况就是,硬件内存这些东西的成本与极致的用户体验,比如更快的响应,操作的流畅感比起来,就目前的条件来看,重要程度是更低的,随着空间可接受度增大,时间可接受程度相对变小,说白了,就是现在空间条件宽裕了(各大设备厂家无脑怼硬件,说明目前空间资源成本相对较低),大家拼的就是速度,谁的算法执行快,谁的产品用户体验更好,谁在竞争中更有优势;

    2.如何计算一个算法的时间复杂度?
    算这个时间复杂度实际上只需要遵循如下守则:

    用常数1来取代运行时间中所有加法常数;
    只要高阶项,不要低阶项;
    不要高阶项系数;

    2.0:常见的时间复杂度:
    按增长量级递增排列,常见的时间复杂度有:
     

    • O(1)—常数阶
    • O(N)—线性阶
    • O(log2N)—对数阶
    • O(nlogn)—线性对数阶
    • O(n^2)—平方阶



    2.1:O(1)—常数阶
    O(1)的算法是一些运算次数为常数的算法。例如:

     

    1

    2

    3

    temp=a;

    a=b;

    b=temp;



    根据守则:
    用常数1来取代运行时间中所有加法常数;
    上面语句共三条操作,单条操作的频度为1,即使他有成千上万条操作,也只是个较大常数,这一类的时间复杂度为O(1);

    2.2:O(N)—线性阶
    O(n)的算法是一些线性算法。例如:
     

    1

    2

    3

    sum=0;                

       for(i=0;i<n;i++)      

           sum++;



    上面代码中第一行频度1,第二行频度为n,第三行频度为n,所以f(n)=n+n+1=2n+1。

    根据守则:
    只要高阶项,不要低阶项目,常数项置为1,去除高阶项的系数:
    所以时间复杂度O(n)。这一类算法中操作次数和n正比线性增长。

    2.3:O(log2N)—对数阶
    什么是对数?
    a^x = N,(a>0 && a!=1),那么x即是以a为底,N的对数,记作
    其中a叫做对数的底数,N叫做真数。

    例1:
     

    01

    02

    03

    04

    05

    06

    07

    08

    09

    10

    private static void 对数阶() {

        int number = 1;//执行1次

        int n = 100;//执行1次

     

        while (number < n) {

            number = number * 2; // 执行n/2

            System.out.println("哈哈");//执行1次

        }

     

    }



    假设n为100,number是1,小于100退出循环。
     

    • 第1次循环,number = 2,2^1。
    • 第2次循环,number = 4, 2^2。
    • 第3次循环,number = 8, 2^3。
    • 第x次循环,number = 2^x


    也就是2^x=n得出x=log₂n。因此它的复杂度为O(logn)。

    例2:
    二分查找;
    比如: 1,3,5,6,7,9;找出7
    如果全部遍历时间频度为n;
    二分查找每次砍断一半,即为n/2;
    随着查询次数的提升,频度变化作表:
     

    2.4:O(nlogn)—线性对数阶
    上面看了二分查找,是LogN的(LogN没写底数默认就是Log2N);
    线性对数阶就是在LogN的基础上多了一个线性阶;
    比如这么一个算法流程:
    数组a和b,a的规模为n,遍历的同时对b进行二分查找,如下代码:

     

    [Bash shell] 纯文本查看 复制代码

    ?

    1

    2

    3

    for(int i =0;i<n;i++)

        binary_search(b);

    }



    2.5:O(n^2)—平方阶
    普通嵌套循环
     

    1

    2

    3

    4

    5

    6

    7

    8

    private static void 普通平方阶(){

        int n = 100;

        for (int i = 0; i < n; i++) {//执行n次

            for (int j = 0; j < n; j++) {//执行n次

                System.out.println("哈哈");

            }

        }

    }



    这种就是2层循环嵌套起来,都是执行n次,属于乘方关系,它的时间复杂度为O(n^2)。

    等差数列嵌套循环
     

    1

    2

    3

    4

    5

    6

    7

    8

    private static void 等差数列平方阶() {

        int n = 100;

        for (int i = 0; i < n; i++) {//执行n次

            for (int j = i; j < n; j++) {//执行n - i次

                System.out.println("哈哈");

            }

        }

    }



    基本式:

    i = 0,循环执行次数是 n 次。
    i = 1,循环执行次数是 n-1 次。
    i = 2,循环执行次数是 n-2 次。

    i = n-1,循环执行的次数是 1 次。
    换算式:

    result = n + (n - 1) + (n - 2) … + 1
    被加数递减,抽象为一个等差数列求n项和的问题,公差为1,带入公式,Sn = n(a1 + an ) ÷2
    result = (n(n+1))/2
    result = (n^2+n)/2
    result = (n^2)/2 + n/2

    粗略计算时间复杂度的三部曲:

    1.去掉运行时间中的所有加法常数。
    没有加法常数,不考虑。
    2.只保留最高阶项。
    最高阶参考上面列出的按增长量级递增排列,于是只需要保留result = (n^2)/2
    3.如果最高阶项存在且不是1,去掉与这个最高阶相乘的常数得到时间复杂度
    除以2相当于是乘以二分之一,去掉它,就得到,result = n^2, 所以这个算法的时间复杂度为O(n^2)。


    3.时间复杂度的优劣对比
    常见的数量级大小:越小表示算法的执行时间频度越短,则越优;
     

    O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)//2的n方<O(n!)<O(nn)//n的n方
    展开全文
  • 算法复杂度分为时间复杂度和空间复杂度。 时间复杂度用于度量算法执行的时间长短;而空间复杂度则是用于度量算法所需存储空间的大小。 目录 时间复杂度 1.时间频度 2.计算方法 3.分类 空间复杂度 算法的时间...

    文章地址:http://lzw.me/a/algorithm-complexity.html

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

    目录

    时间复杂度 

    1.时间频度 

    2.计算方法

    3.分类

    空间复杂度

    算法的时间复杂度(计算实例) 

    算法复杂度的渐近表示法

    一  大O记号

    二  Ω记号

    三  Θ记号

    四  小o记号

    五  例子

    常见排序算法时空复杂度


    时间复杂度 

    1.时间频度 

      一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

    2.计算方法

      1. 一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))
      分析:随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。

      2. 在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))

      例:算法:

      for(i=1;i<=n;++i)
      {
      for(j=1;j<=n;++j)
      {
      c[ i ][ j ]=0; //该步骤属于基本操作执行次数:n的平方 次
      for(k=1;k<=n;++k)
      c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n的三次方 次
      }
      }

      则有 T(n)= n的平方+n的三次方,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级
      则有f(n)= n的三次方,然后根据T(n)/f(n)求极限可得到常数c
      则该算法的 时间复杂度:T(n)=O(n的三次方)

    3.分类

      按数量级递增排列,常见的时间复杂度有:
      常数阶O(1),对数阶O(log2n),线性阶O(n),
      线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),…,
      k次方阶O(nk), 指数阶O(2n) 。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

    空间复杂度

      与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:
      S(n)=O(f(n))
      我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。
     

    算法的时间复杂度(计算实例) 

    算法的时间复杂度
    定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

    当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。

    我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。

    此外,一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。

    “大O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。

    这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。

    O(1)

    Temp=i;i=j;j=temp;

    以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

    O(n^2)

    2.1. 交换i和j的内容

    sum=0; (一次)
    for(i=1;i<=n;i++) (n次)
    for(j=1;j<=n;j++) (n^2次)
    sum++; (n^2次)

    解:T(n)=2n^2+n+1 =O(n^2)

    2.2.

    for (i=1;i<n;i++)
    {
    y=y+1; ① 
    for (j=0;j<=(2*n);j++) 
    x++; ② 
    }

    解:语句1的频度是n-1
    语句2的频度是(n-1)*(2n+1)=2n^2-n-1
    f(n)=2n^2-n-1+(n-1)=2n^2-2
    该程序的时间复杂度T(n)=O(n^2).

    O(n) 

    2.3.
    a=0;
    b=1; ①
    for (i=1;i<=n;i++) ②

    s=a+b;    ③
    b=a;     ④ 
    a=s;     ⑤
    }

    解:语句1的频度:2, 
    语句2的频度: n, 
    语句3的频度: n-1, 
    语句4的频度:n-1, 
    语句5的频度:n-1, 
    T(n)=2+n+3(n-1)=4n-1=O(n).

    O(log2n )

    2.4.

    i=1; ①
    while (i<=n)
    i=i*2; ②

    解: 语句1的频度是1, 
    设语句2的频度是f(n), 则:2^f(n)<=n;f(n)<=log2n 
    取最大值f(n)= log2n,
    T(n)=O(log2n )

    O(n^3)

    2.5.

    for(i=0;i<n;i++)

    for(j=0;j<i;j++) 
    {
    for(k=0;k<j;k++)
    x=x+2; 
    }
    }

    解:当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,…,m-1 , 所以这里最内循环共进行了0+1+…+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+…+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).
     

    我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最坏情况运行时间是 O(n^2),但期望时间是 O(nlogn)。通过每次都仔细地选择基准值,我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中,精心实现的快速排序一般都能以 (O(nlogn)时间运行。

    下面是一些常用的记法:

    访问数组中的元素是常数时间操作,或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3),因为算出每个元素都需要将n对 元素相乘并加到一起,所有元素的个数是n^2。

    指数时间算法通常来源于需要求出所有可能结果。例如,n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了,除非n的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如著名的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况,通常应该用寻找近似最佳结果的算法替代之。

    算法复杂度的渐近表示法

    一个算法的时间复杂度,指算法运行的时间。

    假设数据输入规模是n,算法的复杂度可以表示为f(n)的函数

    一  大O记号

    假设f(n)和g(n)的定义域是非负整数,存在两个正整数c和n0,使得n>n0的时候,f(n)≤c*g(n),则f(n)=O(g(n))。可见O(g(n))可以表示算法运行时间的上界。O(g(n))表示的函数集合的函数是阶数不超过g(n)的函数。

    例如:f(n)=2*n+2=O(n)

    证明:当n>3的时候,2*n +2<3n,所以可选n0=3,c=3,则n>n0的时候,f(n)<c*(n),所以f(n)=O(n)。

    现在再证明f(n)=2*n+2=O(n^2)

    证明:当n>2的时候,2*n+2<2*n^2,所以可选n0=2,c=2,则n>n0的时候,f(n)<c*(n^2),所以f(n)=O(n^2)。

    同理可证f(n)=O(n^a),a>1

    二  Ω记号

    Ω记号与大O记号相反,他可以表示算法运行时间的下界。Ω(g(n))表示的函数集合的函数是所有阶数超过g(n)的函数。

    例如:f(n)=2*n^2+3*n+2=Ω(n^2)

    证明:当n>4的时候,2*n^2+3*n+2>n^2,所以可选n0=4,c=1,则n>n0的时候,f(n)>c*(n^2),所以f(n)=Ω(n^2)。

    同理可证f(n)=Ω(n),f(n)=Ω(1)

    三  Θ记号

    Θ记号介于大O记号和Ω记号之间。他表示,存在正常数c1,c2,n0,当n>n0的时候,c1*g(n)≤f(n)≤c2*g(n),则f(n)=Θ(g(n))。他表示所有阶数与g(n)相同的函数集合。

    四  小o记号

    f(n)=o(g(n))当且仅当f(n)=O(g(n))且f(n)≠Ω(g(n))。也就是说小o记号可以表示时间复杂度的上界,但是一定不等于下界。

    五  例子

    假设f(n)=2n^2+3n+5,

    则f(n)=O(n^2)或者f(n) = O(n^3)或者f(n)=O(n^4)或者……

    f(n)=Ω(n^2)或者f(n)=Ω(n)或者f(n)=Ω(1)

    f(n)=Θ(n^2)

    f(n) = o(n^3)或者f(n)=o(n^4)或者f(n)=o(n^5)或者……

    注:n^2表示n的平方,以此类推。

    常见排序算法时空复杂度

     

     

    排序法

    最差时间分析 平均时间复杂度 稳定度 空间复杂度
    冒泡排序 O(n2) O(n2) 稳定 O(1)
    快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n)
    选择排序 O(n2) O(n2) 稳定 O(1)
    二叉树排序 O(n2) O(n*log2n) 不一顶 O(n)

    插入排序

    O(n2) O(n2) 稳定 O(1)
    堆排序 O(n*log2n) O(n*log2n) 不稳定 O(1)
    希尔排序 O O 不稳定 O(1)
    展开全文
  • 【算法】算法复杂度

    2020-08-18 17:22:53
    算法复杂度是衡量算法难度的尺度。 • 算法需要的资源越多,复杂度越高。计算机的资源,最重要的是运算所需的时间和存储程序和数据所需的空间资源。 • 算法复杂度包括时间复杂度和空间复杂度。 • 复杂问题或...

    1、算法分析

    • 算法复杂度是衡量算法难度的尺度。

    • 算法需要的资源越多,复杂度越高。计算机的资源,最重要的是运算所需的时间和存储程序和数据所需的空间资源。

    • 算法复杂度包括时间复杂度和空间复杂度。

    • 复杂问题或高效算法一般不做算法分析,而是采用基准测试方法。

    • 能够分析清楚的算法,一般是简单或低效算法;

    • 难题(如货郎担问题)及高效算法很难分析清楚。

    2、计算算法复杂度的困难

    • 算法复杂度与问题规模大小有关;
    • 输入数据的分布也会影响算法复杂度。

    算法复杂度评价:
    • 最好、最坏、平均;
    • 通常着重于最坏情况下的算法复杂度。

    精确计算算法复杂度的困难:
    (1)由算法写出程序需要花费很大的精力;
    (2)会因为程序写的好坏,影响算法的质量;
    (3)测试数据很难对各个算法都公正;
    (4)好算法需要反复改进,反复测试,工作量很大。

    3、算法时间复杂度的表示

    • 算法时间复杂度指程序从开始运行到结束需要的时间。
    • 问题规模为n,算法需要的时间为T(n)时,T(n)称为算法的“时间复杂度”。
    • 算法时间复杂度常用大O表示(读为:大圈,Order,big-O)。
    • 算法时间复杂度与输入数据的规模有关。
    • 如,二分查找算法复杂度是O(log n),表示二分查找需要通过log n量级的运算步骤,去查找一个规模为n的数组。
    • 如,算法复杂度为O(f(n)),表示当n增大时,运行时间最多以f(n)的速度增长。也称为渐进复杂度。

    常见算法复杂度级别
    在这里插入图片描述
    算法时间复杂度增长趋势曲线
    在这里插入图片描述

    4、算法时间复杂度计算案例

    【案例】时间复杂度T(n)=O(1)的情况,如:
    • temp=i;
    • i=j;
    • j=temp;
    • 以上语句的频度均为1,程序执行时间是不问题觃模n无关的常数。
    • 算法时间复杂度为常数阶时,记T(n)=O(1)。
    • 如果算法执行时间丌随问题觃模n的增加而增长,即使算法有上千条语句,其执行时间也是一个较大的常数。
    记作T(n)=O(1)
    【例】时间复杂度T(n)=O(n)的情况。
    在这里插入图片描述
    以上算法的时间复杂度为:T(n)=2+n+3(n-1)=4n-1=O(n)。
    【例】时间复杂度T(n)=O(log n)的情况。
    在这里插入图片描述
    设语句2的频度是:f(n),f(n)<=n,f(n)<=log n,取最大值f(n)=log n;
    算法的时间复杂度为:T(n)=2log n +1=O(log n)
    【例】 时间复杂度T(n)=O(n2)的情况。
    在这里插入图片描述
    以上算法的时间复杂度为:T(n)=2n2+n+1 =O(n2)

    5、算法的空间复杂度

    • 算法空间复杂度指程序从开始运行到结束所需的存储空间。
    • 算法空间复杂度包括:
    (1)固定部分
    • 如,程序代码、常量、简单变量等占用空间。
    (2)可变部分
    • 如,处理数据的大小不问题觃模有关。
    • 空间复杂度不时间复杂度计算方法相似;
    • 空间复杂度分析相对简单,所以一般主要讨论时间复杂度。

    展开全文
  • 算法复杂度分析,算法复杂度o(1), o(n), o(logn), o(nlogn) 时间复杂度On和空间复杂度O1是什么意思?
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 94,436
精华内容 37,774
关键字:

算法复杂度