初识复杂度与对数器

时间复杂度

• 务必细分过程，区别出常数操作和与 N 有关的操作。这也要求你对调用的 API 有一定熟悉程度！
• 对于插入排序这样会由于数据状态而影响到算法过程的，一律按最差情况统计复杂度！
• 冒泡和选择排序的算法性能是固定的，不受数据状态影响；而插入会受数据状态影响。后者性能大于前两者。
• 当两算法的复杂度都相等时(比如，冒泡和插入都为$O(N^2)$) ，就需要比拼各自的常数项时间。如何比拼常数项时间：
  放弃理论分析,生成随机数据直接测 。为什么不去理论分析?不是不能纯分析,而是没必要。因为不同常数时间的操作,虽然都是固定时间,但还是有快慢之分的。比如,位运算的常数时间小于算术运算的常数时间,这两个运算的常数时间又小于数组寻址的时间 。所以如果纯理论分析,往往会需要非常多的分析过程（就比如，算术运算在某些时候可转为位运算，详见csapp）。常数时间不考虑在最优解范畴。
• 算法优劣：$O(1)>O(logN)>O(N)>O(N×logN)>O(N^X)>O(X^N)>O(N!)$ ，其中 X 为常数，N 为数据量；

对数器

网页上关于对数器的介绍基本都来自于算法讲师左程云，所以这里不再赘述其他内容，只提供几个关键点：

1. 有一个你想要测的方法 a；
2. 实现一个绝对正确(不管复杂度)的方法 b；
3. 实现一个随机样本产生器；
4. 实现对比算法 a 和 b 的方法；
5. 把方法 a 和方法 b 比对多次来验证方法 a 是否正确；
6. 如果有一个样本使得比对出错，则打印样本进行分析；
7. 当样本数量很多时比对测试依然正确，可以确定方法 a 已经正确。

以下是对数器代码:

//本文件sortTester.h
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;

int* generateRandomArray(int maxVar, int len)
{
	if(maxVar <= 0 || len <= 0)
		return NULL;
	int *arr = new int[len];
	for(int i = 0; i < len; i++)
	{
		arr[i] = rand() % maxVar;
	}
	return arr;
}

int* cpyArr(int* arr, int len)
{
	if(arr == NULL || len <= 0)
		return NULL;
	int* cpy = new int[len];
	for(int i = 0; i < len; i++)
	{
		cpy[i] = arr[i];
	}
	return cpy;
}

bool isEqual(int* arr1, int* arr2, int len)
{
	for(int i = 0; i < len; i++)
	{
		if(arr1[i] != arr2[i])
			return false;
	}
	return true;
}

template<class function>
void sortTester(function func, int times, int maxVar, int maxLen)
{
	srand(time(NULL));
	int len;
	for(int i = 0; i < times; i++)
	{
		len = rand() % maxLen;
		int* arr = generateRandomArray(maxVar, len);
		int* cpy = cpyArr(arr, len);
		int* cpy1 = cpyArr(arr, len);
		sort(arr, &arr[len], [](int a, int b){return a < b;}); //从小到大排序
		func(cpy, len, [](int a, int b){return a<b;});
		if(!isEqual(arr, cpy, len))//打印错误案例
		{
			cout<< "wrong...." << endl;
			cout<< "original : "
			for(int i = 0; i < len; i++)
				cout<< cpy1[i] << " ";
			cout<< endl;
			cout<< "wrong case: "
			for(int i = 0; i < len; i++)
				cout<< cpy[i] << " ";
			cout<< endl;
			return;
		}
		cout<< "success" << endl;
		delete[] cpy;
		delete[] arr;
	}
}

以冒泡排序为例来演示利用对数器进行测试：

#include"sortTester.h"
using namespace std;
template<class T, class cmptor>
void bubbleSort(T* vec, int len, cmptor cmp)
{
	for(int i = 0; i < len-1; i++)
	{	
		for(int k = 0; k < len-1-i; k++)
		{
			if(!cmp(vec[k], vec[k+1]))
				swap(vec[k], vec[k+1]);
		}
	}
}
int main()
{
	typedef bool (*cmp)(int a, int b);
	auto sort = bubbleSort<int, cmp>;
	sortTester(sort, 100, 100000, 10000);	
}