算法基础1：复杂度和简单算法

目录

一.时间复杂度

1.概述

2.时间复杂度表达

3.简便计算时间复杂度

4.注意事项

二.简单算法

1.异或运算

（1）交换操作

（2）异或算法应用1

（3）异或算法应用2

2.插入排序

3.二分法

4.对数器

三.空间复杂度

1.概念

2.空间复杂度计算和表示

（1）计算步骤：

（2）空间复杂度的表示

3.示例代码

（1）空间复杂度O(1)

（2）空间复杂度O(n)

一.时间复杂度

1.概述

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

        时间复杂度为一个算法流程中，常数操作数量的一个指标。常用0(读作big 0)来表示。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那么时间复杂度为0(f(N))。

       时间复杂度表示某个算法运行时间的趋势，可以大致评判程序的效率。 评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”。

2.时间复杂度表达

        列出需要执行程序的次数，写成T(N)=aN²+bN+C的形式。此时，以存在的最高次项作为时间复杂度，因为N趋于无穷时，只有最高次项对结果的影响大。

例如：列出式子为aN³+bN+C，时间复杂度即为O(N³）。

具体的高阶低阶排行如下图：

  如果阶数指标相同，无法通过常数项比较时间复杂度，只能通过实际跑代码区分。

3.简便计算时间复杂度

        一般来说，最内层执行次数最多的语句就决定了整个算法的趋势，通常看最内层语句执行次数的规律即可。

4.注意事项

对于任何算法流程，估计时间复杂度O时，按照最差情况估计。

二.简单算法

1.异或运算

（1）交换操作

此时a和b必须拥有不相同的内存空间，因为同样的内存区域跟自己异或，会直接变成0。

void swap(int,a, int b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

（2）异或算法应用1

问题：一个数组中，只有1个数出现奇数次，其他数均出现偶数次。求出现奇数次的这个数。

解法：定义一个eor = 0,将数组中所有数与其异或，异或出的eor即为解。因为异或运算同一批数，不管顺序如何，异或结果一样。所以等同于偶数次的数先异或。

原理：异或的交换律。

#include
#include
#include
using namespace std;
void solve(int num[]);
int main() {
	//算法问题1：问题：一个数组中，只有1个数出现奇数次，其他数均出现偶数次。求出现奇数次的这个数
	//解法：定义一个eor = 0,将数组中所有数与其异或，异或出的eor即为解。
	int nums[] = { 1,2,1,2,1,3,2,1,2,3,3 };
	solve(nums);
	system("pause");
	return 0;
}
void solve(int num[]) {
	int eor = 0;
	int len = sizeof(num) / sizeof(num[0]);
	for (int i = 0; i