定义

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

学习方法

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

复杂度分析

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

时间复杂度

 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. 只关注循环执行次数最多的一段代码
• 2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

几种常见的时间复杂度

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=$lo{g}_{2}n$，如果代码里面2变为3，则推倒公式为:
$3^x$=n，x=$lo{g}_{3}n$=$lo{g}_{3}2\ast lo{g}_{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 个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

最后

以上就是坦率小鸽子为你收集整理的数据结构和算法入门定义学习方法复杂度分析的全部内容，希望文章能够帮你解决数据结构和算法入门定义学习方法复杂度分析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。