数据结构初阶--算法复杂度（1）
以下我用C语言实现基础的数据结构。
目录
初识数据结构与算法
数据结构
算法
算法效率
练习：轮转数组(不完全版)
时间复杂度
大O的渐进表示法
例一：
例二：
例三：
例四：
例五：
总结：
例六：
例七：
例八：阶乘递归的时间复杂度
初识数据结构与算法
数据结构
数据结构（Data Structure）是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素集合。如：线性表，树，图，哈希等。
- 常见组织数据方式：增删查改。
算法
算法（Algorithm）定义良好的计算过程，取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说就是一系列的计算步骤，用来将输入数据转化成输出结果。
- 输入：乱序数组
- 输出：有序数组
算法有好坏之分--就看算法复杂度
提升数据结构与算法的方法：死磕、画图
算法效率
练习：轮转数组(不完全版)
对于给定的整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。
#include <stdio.h>
void rotate(int* nums,int numsSize,int k)
{
while(k--)
{
int tmp=nums[numsSize-1];
for(int i=numsSize-1;i>0;i--)
{
nums[i]=nums[i-1];
}
nums[0]=tmp;
}
}算法在编写成可执行程序后，运行时需要消耗时间资源和空间（内存）资源。衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
- 时间复杂度：衡量一个算法的运行快慢
- 空间复杂度：衡量一个算法运行所需要的额外空间
时间复杂度
算法的时间复杂度是一个函数式T(N)，而非具体的运行时间数字。它定量描述了该算法的运行时间。
括号中N指代变量，函数式可能为：T(N)=m+n。
这个T(N)函数计算了程序的执行次数。实际看的是循环语句，变量的单次定义可以忽略不计。衡量的是变量对算法效率结果的影响趋势
大O的渐进表示法
推导大O阶规则：
- 时间复杂度函数式T(N)中，只保留高阶项，去掉低阶项。当N不断变大时，低阶项对结果影响越来越小，可以忽略不计。
- 如果最高阶存在且不是1，就去掉这个项目的常数系数，当N不断变大，这个系数对结果影响越来越小，可以忽略不计。
- T(N)中如果没有N相关项目，只有常数项，用1取代所有加法常数。
例一：
void Func1(int N)
{
int count = 0;
int i=0;
for(i=0;i<N;++i)
{
int j;
for(j=0;j<N;++j)
{
++count;
}
}
int k=0;
for(k=0;k<2*N;++k)
{
++count;
}
int M = 10;
while(_M--)
{
++count;
}
}执行基本操作次数：T(N)=n^2+2*n+10,
根据公式，Func1的时间复杂度为：O(N^2)
例二：
void Func2(int N)
{
int count = 0;
int k=0;
for(k=0;k<2*N;++k)
{
++count;
}
int M = 10;
while(_M--)
{
++count;
}
}执行基本操作次数：T(N)=2*N+10
Func2时间复杂度为：O(N)
例三：
void Func3(int N,int M)
{
int count = 0;
int k=0;
for(k=0;k<N;++k)
{
++count;
}
for(k=0;k<N;++k)
{
++count;
}
printf("%d\n",count);
}执行基本操作次数：T(N)=M+N
类似Func3时间复杂度一般默认为：O(N+M)
但非要说也可以分为三种情况：
- M==N M>N M<N： 那么T(N)=2M或者2N 所以O(M)/(N)
- M>>N 那么N为低阶项即T(N)=M 所以O(M)
- M<<N 那么M为低阶项即T(N)=N 所以O(N)
例四：
-
void Func4(int N) { int count = 0; int k=0; for(k=0;k<100;++k) { ++count; } printf("%d\n",count); }
执行基本操作次数：T(N)=100
Func4时间复杂度为：O(1)
例五：
coust char *strchr(coust char * str,char character)
{
coust char* p_begin=s;
while(*p_begin != character)
{
if(*p_begin =='\0')
{
return NULL;
}
p_begin++;
}
return p_begin;
}执行基本操作次数：
- 要查找字符在第一个/前面位置，T(N)=1
- 在最后一个：T(N)=N
- 在中间：T(N)=N/2
Func5时间复杂度：
- 对应最好情况：O(1)
- 对应最坏情况：O(N)
- 对应平均情况：O(N)
总结：
一些算法的时间复杂度存在最坏、最好和最坏情况
最坏：任意输入规模的最大期望运行次数（上界）
最坏，任意输入规模的最小期望运行次数（下界）
平均，任意输入规模的期望运行次数
大O的渐进表示在实际中一般情况关注的是算法的上界，就是最坏运行情况。
例六：
冒泡排序：
void BubbleSort(int* a,int n)
{
assert(a);
size_t end;
for(end = n;end>0;--end)
{
int exchange=0;
size_t i;
for(i=1;i<end;++i)
{
if(a[i-1]>a[i])
{
Swap(&a[i-1],&a[i]);
exchange=1;
}
}
if(exchange==0)
break;
}
}执行基本操作次数：
- 若数组有序：那么T(N)=N
- 有序且降序T(N)=(N*N+1)/2
- 在中间位置：T(N)=(N*(N+1))/2;
T(N) = (n-1)*(1+n-1)/2=n*n-n/2
时间复杂度：
O(N^2)：O(n^2)
例七：
void func5(int n)
{
int cnt = 1;
while(cnt < n)
{
cnt *= 2;
}
}执行基本操作次数：
T(N)=log₂n
时间复杂度：
O(log₂n)
其中关于对数的写法，有时候不像数学一样严谨。log₂n可能会表示为log₂n、logn、lgn
这一方面是因为在计算机中无法输入对数的底数，所以不规范，另一方面是n接近无穷大时，底数对时间复杂度影响不大
例八：阶乘递归的时间复杂度
long long Fac(size_t N)
{
if(0 ==N)
return 0;
return Fac(N-1)*N;
}递归算法的时间复杂度=单次递归的时间复杂度*递归次数
执行基本操作次数：
T(N)=N
时间复杂度：
O(N)
总执行时间=每条语句运行时间 * 执行次数