面试篇之数据结构与算法概述

01.数据结构与算法概述

本节内容概要

  1. 数据结构及算法概念以及用途
  2. 数据结构分类
  3. 算法的5大特征
  4. 算法的时间复杂度与空间复杂度

1.1、概念

1). 数据结构是一门研究数据组织方式的学科,可以帮助我们写出高效优雅的代码。选择适当的数据结构可以提高程序的执行效率(时间复杂度)和存储效率(空间复杂度)

2). 算法是用来操作数据的一种方法,解决某个问题的计算方法、步骤。数据结构是为算法服务的,算法要作用在特定的数据结构之上程序=数据结构+算法

weixin sousuo guanzhu "SpringForAll社区" ,学习更多!!!

1.2、数据结构分类

面试篇之数据结构与算法概述_第1张图片

1).线性结构: 简单的前后关系: 数组、链表、队列和栈

2).树结构:普通树、二叉树

3).图结构:

和非线性结构

  • 线性结构:一对一的关系

    1) 线性结构作为最常用的数据结构,其特点是数据元素之间存在一对一的线性关系
    2) 线性结构有两种不同的存储结构,即顺序存储结构(数组)和链式存储结构(链表)。顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的
    3)  链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
    4) 线性结构常见的有:数组、链表、队列和栈
  • 树结构:一对多的关系
    • 普通树、二叉树面试篇之数据结构与算法概述_第2张图片
  • 图:适合存储多对多的关系面试篇之数据结构与算法概述_第3张图片

1.3、 算法的五大特征

    1. 有穷性:一个算法必须保证可以结束,也即经历一些有限步会结束
    1. 确定性:算法的每个步骤都应该被精确定义,即同样的输入,输出的结果也一样
    1. 输入 :即参数,算法可以有0或者多个输入,即可以有0或者多个参数
    1. 输出 :算法必须有输出,即有0或者多个输出
    1. 可行性: 算法的每一步都是可行的,即可以实现的

1.3、时间复杂度与空间复杂度

时间复杂度:是一个 函数 ,它用来描述该算法的运行时间。通常用O()函数来表示算法的变化趋势

1.3.1、如何计算时间复杂度

我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了

    1. 总复杂度=复杂度最高的那段代码的复杂度,如下
    int cal(int n) {
       int sum_1 = 0;
       int p = 1;
    //时间复杂度 O(n)
       for (; p < 100; ++p) {
         sum_1 = sum_1 + p;
       }
    
       int sum_2 = 0;
       int q = 1;
    //O(n)
       for (; q < n; ++q) {
         sum_2 = sum_2 + q;
       }
     
       int sum_3 = 0;
       int i = 1;
       int j = 1;
    //O(n^2)
    for (; i <= n; ++i) {
         j = 1;
         for (; j <= n; ++j) {
           sum_3 = sum_3 +  i * j;
         }
       }
     
       return sum_1 + sum_2 + sum_3;
     }

    以上代码的时间复杂度按照最多的

    O(n^2)

    1. 只关注执行次数最多的一段代码,如下
    public int cal(int n) {
        int sum = 0;
        int I = 1;
        for (; I <= n; ++i) {
            sum = sum + I;
        }
        return sum;
    }

    我们只关注执行次数最多的for循环,执行了n次,因此这段代码的时间复杂度为

    O(n)

    • 4.平均时间复杂度:因为最好和最坏情况不一样,所以会出现一个平均时间复杂度,如
    1. 乘法法则: 嵌套代码时间复杂度 = 内外嵌套代码时间复杂度的乘积
    // O(n)
    int cal(int n) {
       int ret = 0;
       int i = 1;
       for (; i < n; ++i) {
         ret = ret + f(i);
       }
     }
     //O(n)
     int f(int n) {
      int sum = 0;
      int i = 1;
      for (; i < n; ++i) {
        sum = sum + i;
      }
      return sum;
     }

    上面代码的时间复杂度 = O(n) * O(n) = O(n^2)

    要查找的变量 x 在数组中的位置,有 n+1 种情况:在数组的 0~n-1 位置中和不在数组中,

    面试篇之数据结构与算法概述_第4张图片

1.3.2、时间复杂度分类

面试篇之数据结构与算法概述_第5张图片

时间复杂度耗时:O(1)本文由博客一文多发平台 OpenWrite 发布!

你可能感兴趣的