网站建设 石景山,深圳网站设计开发,牛年起广告公司名字,包头全网营销网站建设好了#xff0c;经过了漫长的时间学习c语言语法知识#xff0c;现在我们到了数据结构的学习。
首先#xff0c;我们得思考一下
什么是数据结构#xff1f;
数据结构(Data Structure)是计算机存储、组织数据的方式#xff0c;指相互之间存在一种或多种特定关系的数据元素…好了经过了漫长的时间学习c语言语法知识现在我们到了数据结构的学习。
首先我们得思考一下
什么是数据结构
数据结构(Data Structure)是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。
算法又是什么
定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果
算法讲究效率
如何衡量一个算法的好坏 如斐波那契数列虽然代码简单但是它的效率高吗
long long Fib(int n)
{
if(n 3)
{return 1;
}return Fib(n-1) Fib(n-2);
} 是先黑色一步一步进去下去算到Fib1时再一步一步返回上去红色
这得花费非常多的时间效率并不高。 因此要衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度空间复杂度
时间复杂度和空间复杂度 时间复杂度和空间复杂度的区别 作用时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间由于目前的空间都很大基本不用担心空间的 时间复杂度 时间复杂度算法的时间复杂度是一个函数 一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度 也就是找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。 请计算一下Func1中count语句总共执行了多少次
void Func1(int N)
{
int count 0;
for (int i 0; i N ; i)
{
for (int j 0; j N ; j)
{ 这里是N^2
count;
}
}
for (int k 0; k 2 * N ; k)
{
count; 这里是2*N
}
int M 10;
while (M--)
{ 这里是10次
count;
}
经过计算我们可以得出是F(N)N^22*N10
其实对于求复杂度我们一般使用大O的渐进表示法现在来介绍下
大O的渐进表示法 1.大O符号是用于描述函数渐进行为的数学符号 2.规则方法 1用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。 最后得到的结果就是大O阶 egN(10000000000000)这应该写成什么呢 答案仍然是O1. 有人会问为啥它这个数那么大了还是用O1表示呢 现在我们来用形象的例子来解释下 假如那里有座泰山我们要铲平 不同视角会不同 我们人的视角觉得它非常大 但是放到太阳系里面就显得非常小了。 同样对于编程也是一样的道理。 通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数 另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数(上界)平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界)例如在一个长度为N数组中搜索一个数据x 最好情况1次找到最坏情况N次找到平均情况N/2次找到 所以我们实际中一般关注的是最坏的情况。
原因同样是以一个形象的例子来解释 约会的预期管理 情人节约会可能到时的时间 最好1700 平均1800 最坏1900 那么因为只有30%的机会准时到 所以是不是选择说1900时最好,把预期拉到最低。 常见时间复杂度计算举例
void Func2(int N)
{
int count 0;
for (int k 0; k 2 * N ; k)
{ 这里是2*N次
count;
}
int M 10;
while (M--) 这里是10次
{
count;
}
printf(%d\n, count);
}
所以函数是不是就是F(N)2*N10
根据大O法得时间复杂度就是O(N) 例子2
// 计算Func3的时间复杂度
void Func3(int N, int M)
{
int count 0;
for (int k 0; k M; k)
{
count; 这里是M次
}
for (int k 0; k N ; k)
{ 这里是N次
count;
}
printf(%d\n, count);
}
函数式F(N)MN
注意这里的M,N都是未知数并不是具体数
所以根据大O法时间复杂度O(MN)
例子3
// 计算Func4的时间复杂度
void Func4(int N)
{
int count 0;
for (int k 0; k 100; k)
{ 这里是100次
count;
}
printf(%d\n, count);
}
函数式F(N)100
根据大O法由于它是常数嘛所以用1代替
所以时间复杂度O(1). 例子4
const char * strchr ( const char * str, int character );
对于指针如果没有具体说一般默认都是O(N) 例子5
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end n; end 0; --end){ 一般没说的话默认N次int exchange 0;for (size_t i 1; i end; i) 因为两个for循环所以是N^2次{if (a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if (exchange 0) 因为这里有了判断它可以改变最好的情况break; 如果没有这句} 最好也是O(N^2)因为它无法知道它已经排序了 } 排序 最好已经排序好大小O(1) X有人说是看一眼就知道它的大小排序了但是你一亿的时候呢你并不知道其他数字2与这个的大小 你是不是也是要一个一个对比下去呢 所以 时间复杂度 O(N) √ 最坏O(N^2) 其实这里不敢数循环因为以后会学更复杂的 N-1 N-2 N-3....3 2 1 等差数列 算出O(N^2) 例子5我们之前写过的二分查找
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n-1;while (begin end){int mid begin ((end-begin)1);if (a[mid] x)begin mid1;else if (a[mid] x)end mid;elsereturn mid;
}return -1;
} 四 第三次 第二次 第一次 我们可以发现这是不是一次查找我们就可以筛选掉一半。 最坏情况区间缩放到一个值时要么找到要么找不到 假设N是数组个数x是最坏查找次数 N/2/2/2/2.../21 折半查找多少次就除多少个2 假设是x次 2^xN xlog N 这里我们先来说明一下 接着我们来看一下二分查找的显著优势 对比 N 1000 100W 10亿 2^101024 O(N) 1000 100W 10亿 2^201024*1024 O(log N) 10 20 30 2^301024*1024*1024 我们可以看到这二分查找极大改变它的时间效率。 但是一个很不友好的一点是它仅仅局限于排序好的数所以我们以后也不太实用 例子6 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
if(0 N)
return 1;
return Fac(N-1)*N;
} 这是不是相当于有N1次ON1 根据大O法时间复杂度O(N) FacN FacN-1 FacN-2 .... Fac(1) Fac(0) 例子七
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{
if(N 3)
return 1;
return Fib(N-1) Fib(N-2);
} 等比数列 -缺失常数 时间O(2^N) 空间ON 对此我们可以得出来 时间一去不复返不可重复利用 空间用了以后要归还可以重复利用。 空间复杂度
1.空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 2.空间复杂度算的是变量的个数而不是程序占用了多少bytes的空间因为这个也没太大意义
注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。
3.空间复杂度的使用规则也是大O法 空间复杂度举例
例子1
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;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;}
}
我们上面说了空间复杂度算的是变量的个数
我们看到了上面用了三个变量endexchangei。 --O(3)
根据大O法O(1). 例子2绝大多数空间复杂度都是O(1)或O(N) 计算Fibonacci的空间复杂度返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if(n0)return NULL; long long * fibArray (long long *)malloc((n1) * sizeof(long long));fibArray[0] 0; 为什么要多加1因为数组从0开始fibArray[1] 1; for (int i 2; i n ; i){fibArray[i] fibArray[i - 1] fibArray [i - 2];}return fibArray;
} 上面创建了n1个空间 所以根据大O法O(N) 例子3
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{
if(N 0)
return 1;
return Fac(N-1)*N;
} 值得注意的是 递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间 函数在栈的开辟函数栈帧时是单独开辟的。调用本身时会再2开辟一块空间作为新的函数栈帧但是在此外并没有创建额外的变量所以会认为创建的每一块栈帧空间复杂度变量是常数个。 举个形象例子 空间销毁是把那个使用权还给操作系统了并不是说这块空间就没了 内存的申请就相当于 住酒店一样当这房间不用了这不是说把它炸 所以参数从N到0共递归了N1次 根据大O法O(N 例子6
同样斐波那契数列也是一样。
long long Fib(size_t N)
{
if(N 3)
return 1;
return Fib(N-1) Fib(N-2);
} 空间销毁是把那个使用权还给操作系统了我们上面说过空间是可以重复使用的
调用某个函数结束后再次调用此函数所用的空间与上一次的函数空间是同一个。
所以同样是递归了N-1次
由大O法ON。 大O的常见的变化表 祝福语
最后的最后希望我们都能战胜困难一步一步地坚持下去为以后拿到好offer
