当前位置：首页 > news >正文

数据结构笔记01

news 来源：原创 2024/5/6 3:49:24

文章目录

📊📊一时间复杂度和空间复杂度
- 1.1算法效率
- 1.2 刷题
- - 题目

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

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;

F(N)=N^2+11

T(N)=O(N^2)

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

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;
}

T(n)=logn 最好的情况：O(1)
空间效率
- 又称空间复杂度；衡量一个算法所需要的额外空间
- 递归算法的空间复杂度：递归的栈帧深度，因为递归函数要建立战阵递归需要消耗空间。
- 斐波那契数列的空间复杂度是O(2^n)。
总结：
- 时间复杂度不计算时间，计算大概的运算次数。
- 空间复杂度不计算空间，计算大概定义的变量个数。

1.2 刷题

题目

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

思路梳理：因为要求了时间复杂度是O(n)，所以排除冒泡排序的方法。也不能使用二次遍历的方法。
提示:根据题目的提示：其他数字都出现了两次，想到可以利用异或的方法将出现两次数字变为0，而0与两个出现一次的数字异或得到一个新的数字，但在其二进制位上的能有规律可循
具体的图文讲解：

在这里插入图片描述

代码

#include<iostream>
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;
}