数据结构笔记01

📊📊一时间复杂度和空间复杂度

1.1算法效率

• 时间效率

  • 又称时间复杂度；衡量一个算法的运行速度，

  • 定义：算法的时间复杂度是一个函数，定量描述该算法的运行时间。一个算法的运行时间于其中语句的执行次数成正比例。算法中的基本操作的执行次数。为算法的时间复杂度

  • 大O的渐进表示法:大O符号(Big O notation):适用于描述函数渐进行为的数学符号。

  • 如下面的栗子：

   int count=0;
   for(int i=0;i<N;i++){
       for(int j=0;i<N;j++) {
           count++;
       }
   }
   int M=10;
   while(M--) {
       count++;
   }
   cout<<count<<enld;
1
2
3
4
5
6
7
8
9
10
11

F(N)=N^2+11

T(N)=O(N^2)

  for(int i=0;i<N;i*2) {
  	cout<<i;
  }
1
2
3

F(N)=logN【注意是以2为底数的对数】

T(N)=O(logN)

• 推到大O阶方法

  • 用常数1取代运行中的所有加法常数
  • 在修改后的运行此函数中 ，只保留最高结束
  • 如果最高阶数存在且不是1，则去除其系数，即可

• 默认情况下，我们关注的是算法的最坏运算效率

• 举例：

• //Binarysearch
  int Binarysearch(int* a,int n,int x) {
      assert(a);
      int begin=0;
      int end=0;
      while(begin<end) {
          int mid=begin+((end-begin)>>1);
          if(x>a[mid]) {
              begin=mid+1;
          }
          else if(x<a[mid]) {
              end=mid;
          }
          else {
              return mid;
          }
      }
      return -1;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

• T(n)=logn 最好的情况：O(1)

• 空间效率

  • 又称空间复杂度；衡量一个算法所需要的额外空间
  • 递归算法的空间复杂度：递归的栈帧深度，因为递归函数要建立战阵递归需要消耗空间。
  • 斐波那契数列的空间复杂度是O(2^n)。

• 总结：

  • 时间复杂度不计算时间，计算大概的运算次数。
  • 空间复杂度不计算空间，计算大概定义的变量个数。

1.2 刷题

题目

一个整型数组nums里出两个数字之外，其他数字都出现两次。请找出这两个只出现了一次的数字。要求时间复杂度O(n)，空间复杂度O(1)

• 思路梳理：因为要求了时间复杂度是O(n)，所以排除冒泡排序的方法。也不能使用二次遍历的方法。

• 提示:根据题目的提示：其他数字都出现了两次，想到可以利用异或的方法将出现两次数字变为0，而0与两个出现一次的数字异或得到一个新的数字，但在其二进制位上的能有规律可循

• 具体的图文讲解：

• 代码

#include
using namespace std;
int main() {
   int arr[] = {1,3,5,1,8,7,9,7,6,6,9,8};
   int ret = 0;
   //遍历数组将所有的数字进行异或
   for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
   	ret ^= arr[i];
   }
   //找出ret的第m位为1的位
   int m = 0;
   while (m < 8 * sizeof(int)) {
   	//利用与运算寻找二进制位是1的第m位的m
   	if (ret & (1 << m)) {
   		break;
   	}
   	else {
   		m++;
   	}
   }
   //分组 相同的数字必然分为一组，经过以后运算变为0，而0与最终值进行异或结果不变
   int num1 = 0, num2 = 0;
   for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
   	if (arr[i] & (1 << m)) {
   		num1 ^= arr[i];
   	}
   	else {
   		num2 ^= arr[i];
   	}
   }
   cout << num1<<endl;
   cout << num2<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

• 题目二

  • 设某算法的计算时间表示为递推关系T(n)=T(n-1)+n(n为正整数)及T(0)=1,则该算法的时间复杂度为T(n)=O（?）

  • 解题

    • T(n)=T(n-1)+n
    • T(n)=T(n-2) +(n-1)+n
    • T(n)=T(n-3)+(n-2)+(n-1)+n
    • T(n)=T(1)+2+3+···+(n-2)+(n-1)+n
    • T(n)=T(0)+1++2+3+···+(n-2)+(n-1)+n
    • T(n)=1++1++2+3+···+(n-2)+(n-1)+n
    • T(n)=1+n*(n+1)/2
    • T(n)=n^2/2+n/2+1
    • T(n)=O(n^2)