水利建设相关网站,wordpress 相册主题,怎样做网站api接口,pc网站开发获取位置文章目录 一、数据结构和算法简介二、算法复杂度1. 时间复杂度2. 空间复杂度 一、数据结构和算法简介
数据结构是计算机存储、组织数据的方式#xff0c;指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用#xff0c;所以我们要学… 文章目录 一、数据结构和算法简介二、算法复杂度1. 时间复杂度2. 空间复杂度 一、数据结构和算法简介
数据结构是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用所以我们要学习各种各样的数据结构比如线性表、树、图、哈希等等。
算法是定义良好的计算过程。简单来说算法就是一系列的计算步骤用来将输入数据转换成输出结果。衡量一个算法的好坏需要从算法的复杂度来分析。
二、算法复杂度
算法在编写成可执行程序后运行时需要耗费时间资源和空间内存资源因此衡量一个算法的好坏一般是从时间和空间两个维度来看即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢空间复杂度主要衡量一个算法运行所需要的额外空间。
1. 时间复杂度
在计算机科学中T(N)描述了该算法的指令执行次数并不是计算程序的运行时间。因为一个程序的运行时间不仅关乎算法本身还有编译器版本、机器配置新旧等等因素。 T(N)计算了程序的执行次数假设每句指令执行时间基本一样实际有差别但是微乎其微那么执行次数和运行时间就成等比关系执行次数就能代表程序运行时间效率的优劣。比如对于同一个问题算法a的T(N)N算法b的T(N)N2那么算法a的时间效率优于算法b。
计算时间复杂度要注意由于CPU一秒可以处理上亿条代码指令所以变量的单次定义语句可以忽略时间复杂度只计算循环语句。而我们计算时间复杂度只是想比较算法程序的增长量级也就是N不断变大时T(N)的差别而**常数项和低阶项对结果的影响很小甚至最高项的系数也可以忽略影响所以我们只保留最高项并且它的系数视作1。如果T(N)中没有任何关于N的项时间复杂度就是1。复杂度的最终表示通常使用O的渐进表示法。** 例如 T(N)3N22N10则时间复杂度为O(N2) T(N)5N3N25N则时间复杂度为O(N3) T(N)6则时间复杂度为O(1)
来几个例子分析就懂了
void Func1(int N)
{ int count 0; //忽略for (int i 0; i N ; i) { for (int j 0; j N ; j) { count; //N^2次} } for(int k 0; k 2*N ; k) { count; //2N次} int M 10; //忽略while(M--) { count; //10次}
}
//T(N)N^22N10 时间复杂度为O(N^2)void Func2(int N)
{int count 0;for(int k0; k100; k){count; //100次} printf(%d,count);
}
//T(N)100 时间复杂度为O(1)void func3(int n)
{int cnt 1;while(cnt n)cnt * 2;
}
//n2时执行次数为1。n4时执行次数为2。n16时执行次数为4 ......
//假设执行次数为x则2^xn。xlog n时间复杂度为O(logN)
//对数的底数对结果的影响也可以忽略因此不管底数是多少都可以省略不写都表示为log nlong long func4(size_t N)
{if(N0)return 1;return func4(N-1)*N;
}
//递归也是一种循环递归算法的时间复杂度是单次递归的时间复杂度乘递归次数
//时间复杂度为O(1)×N O(N)void func5(int N, int M)
{int count 0;for(int k 0; kN; k)count; //N次for(int k 0; kM; k)count; //M次printf(%d, count);
}
//T(N)NM
//若NM则时间复杂度为O(N)。若M远大于N则为O(M)。若N远大于M则为O(N)除此之外有些算法的时间复杂度还存在最好、平均、最坏情况。最好情况是任意输入规模的最小运行次数下界最坏情况是任意输入规模的最大运行次数上界。一般情况下我们都关注算法的最坏运行情况。比如冒泡排序算法就存在这样的情况 最好情况是数组已经有序时间复杂度就是O(N)最坏情况是数组完全逆序时间复杂度是O(N2)因此冒泡排序的时间复杂度取最差情况O(N2)
2. 空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中需要额外临时开辟的空间。空间复杂度并不是程序运行所占用的内存大小计算的是变量的个数。大多数算法使用的是有限个变量所以空间复杂度为O(1)。但对于递归算法递归的空间复杂度等于单词递归的空间复杂度乘以递归次数即O(1)×NO(N) 在实际算法题目中我们尤其关注时间复杂度空间复杂度就不是特别重要了。 本篇完感谢阅读
