美文网首页
数据结构和算法入门

数据结构和算法入门

作者: xiaolyuh | 来源:发表于2022-06-13 20:39 被阅读0次

    定义

    数据结构就是指一组数据的存储结构,算法就是操作这组数据的一组方法。

    学习方法

    数据结构和算法不用死记,我们要学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”,尽量手写实现。


    image.png

    复杂度分析

    数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,如何让代码更省存储空间。所以时间和空间就是衡量一个算法执行效率的总要指标。

    时间复杂度

     int cal(int n) {
       int sum = 0;
       int i = 1;
       for (; i <= n; ++i) {
         sum = sum + i;
       }
       return sum;
     }
    

    这段代码的时间T(n)=2+2n,这里的低阶、常量、系数都不会左右代码执行时间的增长趋势,所以可以直接忽略,即这段代码的时间复杂度为O(n)。

    大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

    时间复杂度分析

      1. 只关注循环执行次数最多的一段代码
      1. 加法法则:总复杂度等于量级最大的那段代码的复杂度
      1. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    几种常见的时间复杂度

    O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^3)...

    1. O(1)
      只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)。
    2. O(logn)、O(nlogn)
     int i=1;
     while (i <= n)  {
       i = i * 2;
     }
    

    这段代码的执行次数为x,2^x=n,x=log_2{n},如果代码里面2变为3,则推倒公式为:
    3^x=n,x=log_3{n}=log_32*log_2{n}

    在采用大 O 标记复杂度的时候,可以忽略系数,即时间复杂度都为O(logn)

    最好、最坏、平均时间复杂度

    // n表示数组array的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) {
           pos = i;
           break;
        }
      }
      return pos;
    }
    

    这段代码是在一个数组中找到元素x的位置,找到过后结束。
    这里最好和最坏分别是X元素第一个位置和在最后一个位置,即O(1)和O(n)。这里极端情况发生概率不是很大,所以我们需要计算平均时间复杂度。

    要查找的变量 x 在数组中的位置,有 n+1 种情况:在数组中和不在数组中。我们把每种情况下,查找需要遍历的元素个数累加起来,然后再除以 n+1,就可以得到需要遍历的元素个数的平均值,即:
    1+2+3+……+n+n/n+1 = n(n+3)/2(n+1),即时间复杂度为O(n)

    空间复杂度

    表示算法的存储空间与数据规模之间的增长关系。

    
    void print(int n) {
      int i = 0;
      int[] a = new int[n];
      for (i; i <n; ++i) {
        a[i] = i * i;
      }
    }
    

    这里i=0申请了一个空间,但是这是一个常量不能左右趋势,所以这里忽略,下一行代码申请了一个数组空间,且申请的空间会随着n的变大而变大,后续代码没有申请新的空间了,即这段代码的空间复杂度为O(n)。

    我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )。
    存储数据需要一个大小为 n 的数组,并不是说空间复杂度就是 O(n)。因为,这 n 个空间是必须的,无法省掉。所以我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。

    相关文章

      网友评论

          本文标题:数据结构和算法入门

          本文链接:https://www.haomeiwen.com/subject/pqpomrtx.html