时间复杂度

在学习时间复杂度之前我们先了解一下常数操作。

常数时间操作

基本概念

一个操作如果和样本的数据库量没有关系，每次都是固定时间内完成的操作，叫做常数操作。

概念模糊难懂，拿来举一些🌰。

首先是数组的寻址，一个常数操作的时间复杂度。

1
int a = arr[i];

我们熟悉的四则运算+ - * /这些也都是常数操作。

1
2
a+b;
a-b;

链表的寻址操作就不是一个常数操作的时间复杂度，因为寻址时会连续调用之前的内容。

1
int b = list.get[i];

时间复杂度

在常数操作的表达式中，忽略低阶项，只要最高阶，且忽略高阶系数。如果剩下的部分为f(N)则时间复杂度为：

直接看概念很恶心不如直接上例子

那这里举一个大家都知道的选择排序，选择排序的机制时，依次遍历从头开始的数字，找到最小的数，与之交换位置。来画一张图，假设数组中有N个元素。

img

可能会有疑问啊，O是什么意思呢？

在数学中O所指的是最大上限。

平均时间复杂度和最好时间复杂度

在学习计算机时，以下两者，并不会经常使用，仅供参考。

平均时间复杂度θ()

最好时间复杂度Ω()

时间复杂度的比较

第一种，也是很简单的一种，直接比较阶数。

这两者相比，显而易见的b<a，在时间复杂度上，b优于a。

第二种，当阶数相同时，比较常数项。

那么怎么验证呢？上手跑一下（简单粗暴）。

来举个例子实操一下

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
#include <iostream>
using namespace std;
void test01()
{
    int N=1000;
    int a=0;
    for(int 1=0;i<N;i++)
    {
        a=2+5;
        a=4*7;
        a=6*8;
    }
}
void test02()
{
    int N=1000;
    int a=0;
    for(int 1=0;i<N;i++)
    {
        a=3|6;
        a=3&4;
        a=4^786;
    }
}
int main()
{
    
}

这两个例子都是时间复杂度为O(N)的算法，但是比较的话，只能通过实际运行来比较。

估计时间复杂度

在估计时间复杂度时，请按照最差的情况下去考虑。为什么这么说呢？还是以选择排序举例子。

当一个数组所有的数按照从大到小，有序排列，那么要用选择排序改成从小到大，那么很显然，他的时间复杂度是O(N^2)，那么给一个从小到大排列好的数组，用选择排序，改成从小到大排列，那么它的时间复杂度就是O(N)。这两者的时间复杂度可谓是天壤之别，因此在做题时，估计时间复杂度，请按照最差的情况估计

小结

评价一个算法流程的好坏，优先看时间复杂度的指标，然后再根据不同数据样本下的实际运行时间，也就是“常数项时间”，进行对比。

二分法

1.在一个有序数组里找到指定的一个数

img

Master公式

上图的二分法，就可以使用Master公式，这个公式需要具体问题具体分析。二分法的时间复杂度如下

空间复杂度

还是拿选择排序来举例子

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
#include <iostream>
using namespace std;

void selectionSort(int arr[], int n)//数组，以及数组元素个数
{
    for (int i = 0; i < n - 1; i++)
        //开辟了一个 i 的空间
    {
        int minIndex = i;
        //每次使用完后释放
        for (int j = i + 1; j < n; j++)// i~n-1上寻找最小值的下标
            //开辟了一个 j 的空间
        {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;//确定下标
        }
        swap(arr,j,minIndex);
    }
}
void swap(int a[],int i,int j)
{
    a[i]=a[i]^a[j];
    a[j]=a[i]^a[j];
    a[i]=a[i]^a[j];
}
int main()
{
    return 0;
}

因此，这段代码中，都是使用有限个变量来维持代码的运行，分配的空间不会随着处理数据量的变化而变化，因此他的空间复杂度为O(1)

C++的就先记住这么多就即可。

小技巧：异或运算

在这里给大家讲一个交换数值的小技巧（赘述的有些多，因为我觉得是非常好用的东西），但是会用到异或运算，那先来讲一下异或运算。

异或运算的原理是，相同为0，不同为1，并且也可以将异或运算理解为无进位相加1^1=0,1^0=1

假设二进制数a=10110,b=00111

则a^b=10001。

异或运算的性质

  1. O^N=N N^N=0
  2. 满足交换律和结合律

回到原代码中，为了直观一点我们假设a=甲,b=乙。

1
2
3
4
5
6
7
8
void swap(int a,int b)
{
    //a=甲 b=乙
    a=a^b;//a=甲^乙, b=乙
    b=a^b;//a=甲^乙, b=甲^(乙^乙)=> b=甲^0=> b=甲
    a=a^b;//a=甲^乙^甲=> a=乙^(甲^甲)=> a=0^乙=> a=乙, b=甲
    //a=乙 b=甲
}

这样书写，有一个限制，那就是a和b所代表的值可以一样但是，内存必须为两块不一样的内存空间，因为内存空间相同的情况，是自己与自己进行异或运算，会把自己刷成0。

好，既然已经学会了异或运算的骚操作，那么接下来，运用这些知识完成以下题目。

要求时间复杂度为O(N)，空间复杂度为O(1)。

1.在一个数组中，已知有一种数出现了奇数次，其余的数均出现偶数次，找到这一种数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
void test01(int arr[], int n)
{
    int eor = 0;
    for (int i = 0; i < n; i++)
    {
        eor = eor ^ arr[i];
    }
    cout << eor;
}
int main()
{
    int n;
    cin >> n;
    int a[10001];
    for (int i = 0; i < n; i++)cin >> a[i];
    test01(a,n);
    return 0;
}

2.在一个数组中，已知有两种数出现了奇数次，其余的数均出现偶数次，找到这两种数。

该题的解题原理是，假设两个数为a,b,根据刚才的代码易证eor=a^b，则eor中一定会有一个位数为1，假设这个，位数为8，将第8位为1的数放到一起，为0的放在一起，之后设定一个eor'让其再依次异或任意一组数，则得出来的就是a或者b（可以自己动笔画一画，因为其他的数都是偶数，不会影响结果），再将eor与eor'异或，则得出来的就是b或者a

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
34
35
36
37
38
#include <iostream>
using namespace std;
void test02(int a[],int n)
{
	int eor = 0;
	//结束之后 eor =a^b
	for (int i = 0; i < n; i++)
	{
		eor^ a[i];
	}
	// 因为a b 为两个不一样的数
	//eor 必然有一个位置是1
	//因此只需要提取其中的一个1就行
	//提取最右侧的1
	int rightOne = eor & (~eor + 1);
	//定义eor'
	int eor2 = 0;
	//eor'与某位为1的所有数异或
	for (int i = 0; i < n; i++)
	{
		if ((a[i] ^ rightOne) == 1)
		//判断该位上是否为1，是则异或
		{
			eor2 ^= a[i];
		}
	}
	//a b 输出
	cout << eor << " " << (eor2 ^ eor) << endl;
}
int main()
{
	int n;
	int a[10001];
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	test02(a,n);
	return 0;
}