时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所消耗的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。
请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{
int count = 0;
for(int i = 0;i < N;++i)
{
for(int j = 0;j < N;++j)
{
++count;
}
}
for(int k = 0;k < 2 * N;++k)
{
++count;
}
int M = 10;
while(M--)
{
++count;
}
printf("%d
",count);
}
它的复杂度是跟一个N相关的函数式
从上往下看，第一个循环外面循环N次，里面也循环N次，所以第一个循环复杂度也就是F(N)=N*N
第二个循环是循环2倍的N，所以也就是2*N，加上第一个循环，复杂度也就是F(N)=N*N+2*N
第三个循环，因为M是确定的，所以加10就可以了，复杂度F(N)=N*N+2*N+10
算出来这个表达式以后再去给他值
当N是10的时候，F(N)=10^2+2*10+10=130
当N是100的时候，F(N)=100^2+2*100+10=10210
当N是1000的时候，F(N)=1000^2+2*100+10=1002010
把表达式简化，只关注影响最大的项，也就是F(N)=N^2，N越大，2*N+10对结果的影响越小,N^2的占比也越大
实际中我们计算空间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
先计算精确的，再计算对结果影响最大的保留下来就行(不是这个准确的值，而是这个值的估算)
那么Func1的时间复杂度：O(N^2)
大O的渐进表示法
大O符号(Big O notation):是用于描述函数渐进行为的数学符号。推到大O阶方法：
1.用常数1取代运行时间中所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3.如果高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
//计算实Func2的时间复杂度？
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N; ++K) {
++count;
}
int M = 10;
while (M--) {
++count;
}
printf("%d
", count);
}
这题的时间复杂度为O(N),精确的算法是2N+10，N越大10对结果的影响也就越小，当N无限大的时候2N和N是一个级别，像上面说的，高阶项存在且不是1，所以去除这个相乘的常数所以为O(N)
计算Func3的时间复杂度？
void Func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; ++k) {
++count;
}
for (int k = 0; k < N; ++K) {
++count;
}
printf("%d
", count);
}
这段代码的时间复杂度是O(M+N)
一般情况下时间复杂度计算时间未知数都是用的N但是也可以是M、K、X等等其它的
如果M远大于N，结果就是O(M)
如果N远大于M，结果就是O(N)
如果M和N差不多大，结果就是O(M)或O(N)
没有说名M和N的大小关系，结果就是O(M+N)
计算Func4的时间复杂度？
void Func4(int N) {
int count = 0;
for (int k = 0; k < 100; ++k) {
++count;
}
printf("%d
", count);
}
这题的时间复杂度为O(1)
因为没有未知数了，K<100是个常数，也就是把常数换成1，所以结果是O(1)
O(1)不是代表算法运行一次，是常数次
计算strchr的时间复杂度?
const char * strchr (const char * str, int character);
这段代码是查找字符的库函数
while(*str)
{
if(*str==character)
{
return str;
}
else
++str;
}
最好的情况是1，平均的情况是N/2，最坏的情况是N
当一个算法随着输入不同，时间复杂度不同，时间复杂做悲观预期，看最坏的情况，所以是O(N)
计算冒泡排序的时间复杂度？
void bubblesort(int *a, int n) {
assert(a);
for (size_t end = n; end > 0; --end) {
for (size_t i = 1; i < end; ++i) {
if (a[i - 1] > a[i]) {
Swap(&a[i - 1], &a[i])
exchange = 1;
}
}
if (exchange == 0)
break;
}
等差数列，比较次数是N-1，N-2，N-3……
精确的时间复杂度是F(N)=N*(N-1)/2
N阶数不一样，我们只去看阶数最高的那一项，所以时间复杂度是:O(N^2)
int Binarysearch(int *a,int n,int x)
{
assert(a);
int begin=0;
int end=n;
while(begin<end)
{
int mid=begin+((end-begin)>>1)
if(a[mid]<x)
begin=mid+1;
else if(a[mid]>x)
end=mid;
else
return mid;
}
return -1;
}
这个时间复杂度是O(log以2为底N次方) O(log2N)
假设我们要查找x次,因为每次都折半也就是2^x次，也就是x=log2N