金坛建设局网站,如何登陆工商局网站做变更,wordpress如何备份数据库,海珠区做网站的公司友友们大家好啊#xff0c;今天开始正式学习数据结构与算法有关内容#xff0c;后续不断更新数据结构有关知识内容#xff0c;希望多多支持#xff01; 数据结构#xff1a; 数据结构是用于存储和组织数据的方式#xff0c;以便可以有效地访问和修改数据。不同的数据结构… 友友们大家好啊今天开始正式学习数据结构与算法有关内容后续不断更新数据结构有关知识内容希望多多支持 数据结构 数据结构是用于存储和组织数据的方式以便可以有效地访问和修改数据。不同的数据结构适用于不同类型的应用并且具体的数据结构可以大幅影响程序的性能。数据结构分为两大类线性数据结构和非线性数据结构。 算法 算法是完成特定任务的一系列操作步骤是解决问题的明确规范。算法的效率通常通过时间复杂度和空间复杂度来评估即算法执行所需的时间和空间资源。 那么本节课我们进入第一节复杂度 复杂度 时间复杂度大O的渐进表示法常见时间复杂度计算举例 空间复杂度例十计算Fibonacci的空间复杂度 算法效率 算法效率通常是指算法运行所需的资源量评价算法效率主要依据两个重要指标时间复杂度和空间复杂度。 时间复杂度 时间复杂度是在计算机科学中衡量一个算法执行所需时间的量化指标。更准确来说它不直接度量实际的时间如秒或毫秒而是衡量算法需要执行的操作步骤数量。计算时间复杂度通常假设每个基本操作的执行时间是固定和相同的即使在现实中不同的操作可能需要不同的时间。算法中的基本操作的执行次数为算法的时间复杂度 即找到某条基本语句与问题规模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\n, count);
}Func1 执行的基本操作次数F(N)N22*N10;
N10,F(N)130N100,F(N)10210N1000,F(N)1002010
实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。
大O的渐进表示法 大O渐进表示法是数学和计算机科学中用来描述函数增长率的一种表示方法。它是分析算法复杂度如时间复杂度和空间复杂度时最常用的工具之一。大O表示法通过忽略常数因子和低阶项专注于描述最主要的影响因素从而提供了一种比较算法效率的方法。 定义 大O符号记作O(f(n))表示随着输入大小n的增加算法的运行时间或所需空间的增长率与f(n)增长率相同或者更慢。在这里f(n)是一个数学函数代表随着输入规模n的变化算法的资源消耗如何变化。 关键概念 最坏情况分析大O通常表示最坏情况下的复杂度即算法在任何输入上的性能不会比这个界限更差。 渐进上界大O表示的是一个上界说明了算法复杂度的一个上限。 忽略非主要项在大O表示法中我们只关注主要项即最大影响项忽略常数因子和低阶项。
推导大O阶方法
用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶
有些算法的时间复杂度存在最好、平均和最坏情况例四
最坏情况任意输入规模的最大运行次数(上界)平均情况任意输入规模的期望运行次数最好情况任意输入规模的最小运行次数(下界)
例如上述例题 Func1 执行的基本操作次数F(N)N22*N10;
使用大O的渐进表示法以后Func1的时间复杂度为O(N2)
N 10 F(N) 100N 100 F(N) 10000N 1000 F(N) 1000000
通过上面我们会发现大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\n, count);
}基本操作执行了2N10次通过推导大O阶方法知道时间复杂度为 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\n, count);
}基本操作执行了MN次有两个未知数M和N时间复杂度为 O(NM)
例三计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}基本操作执行了10次通过推导大O阶方法时间复杂度为 O(1) O(1)代表常数次 例四计算strchr的时间复杂度
const char * strchr ( const char * str, int character )
{
while(*str)
{if(*strcharacter)return str;str;
}
}这道题就涉及最好情况平均情况和最坏情况 最好情况 最好情况发生在要查找的字符 character 正好是字符串 str 的第一个字符。此时循环会在第一次迭代时找到匹配立即返回指向该字符的指针。在这种情况下该函数的时间复杂度为 O(1)因为无论字符串多长只需进行一次比较操作。 平均情况 平均情况会假设字符在字符串中均匀分布或者一定概率出现在任何位置。由于字符可以出现在字符串的任何位置因此平均而言我们可能需要检查字符串的一半才能找到字符或确定字符不在字符串中。平均来看时间复杂度与字符串的长度成正比即 O(N/2)但由于大O表示法忽略常数因子因此简化为 O(N)其中 N 是字符串的长度。 最坏情况 最坏情况发生在两种情况下 要查找的字符不存在于字符串中则必须遍历整个字符串直至终结符 ‘\0’进行 N 次比较其中 N 是字符串的长度。 要查找的字符正好是字符串的最后一个字符紧邻终结符 ‘\0’这同样需要遍历整个字符串。
时间复杂度一般看最坏所以时间复杂度为 O(N)
例五计算BubbleSort的时间复杂度
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;}
}这道题中有两层循环 最坏的情况发生在数组完全逆序。在这种情况下我们需要对每一个元素做完整的n-1次比较和可能的交换然后是n-2次直到最后一次比较。集合中的比较次数 T 可以用以下等式来表示
T (n-1) (n-2) ... 2 1 n(n-1)/2当 n 逐渐增加到非常大时n2项占据了主导因此我们可以将时间复杂度简化为 O(n2)
例六计算BinarySearch的时间复杂度**二分查找**
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-1;elsereturn mid;}return -1;
}在每次迭代中二分查找都会将搜索范围减半。如果数组的大小为n则迭代如下
第一次迭代后搜索范围减为n/2。第二次迭代后搜索范围减为n/4。…
这一过程持续进行直到搜索范围无法再分割即begin end。划分过程的次数可以用对数函数表示
n, n/2, n/4, ..., 1当我们达到1时相当于进行了k次迭代那么n/2k 1。解这个等式得到n 2k。取对数可得k log₂(n)。
因此二分查找的时间复杂度是O(log n)。
注意这里的对数底数是2是因为每次迭代都将搜索区间分为两部分。二分查找的效率与目标值的实际位置无关从最坏情况来看总是O(log n)。
例七 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
if(0 N)
return 1;
return Fac(N-1)*N;
}每次递归调用减少 N 的值直到 N 达到 0。对于每个 N函数只进行一次递归调用。因此如果初始值为 N那么会有 N 次递归调用。所以这个函数的时间复杂度是 O(N)。
例八 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{
if(N 3)
return 1;
return Fib(N-1) Fib(N-2);
}以 Fib(5) 为例其递归调用树大致如下 Fib(5)/ \Fib(4) Fib(3)/ \ / \
Fib(3) Fib(2) Fib(2) Fib(1)/ \
Fib(2) Fib(1)从这个树状结构中我们可以看到
Fib(5) 分解为 Fib(4) 和 Fib(3)Fib(4) 分解为 Fib(3) 和 Fib(2)Fib(3) 分解为 Fib(2) 和 Fib(1)
以此类推直到基础情况 Fib(1) 或 Fib(2)返回 1。
注意在这棵树中Fib(3) 被计算了两次Fib(2) 被计算了三次。随着 N 的增大重复计算的问题会指数性增长。
在这样的递归调用中每增加一个 N递归树的层数加一每一层的结点数几乎是上一层的两倍除了在接近底部当 N 小于 3 时不再继续拆分。
因此如果我们考虑每个函数调用是树中的一个节点那么整个递归过程涉及的节点总数即函数调用的总数大约是一个满二叉树中的节点数这是因为除了最底层几乎每个节点都会分裂成两个子节点。
满二叉树的节点总数与树的深度在这里即N有关大约是 2N为简化分析这里忽略了精确的计数特别是在树的最底层。因此递归解决方案的时间复杂度被认为是指数级的即 O(2N)。
空间复杂度 空间复杂度是一个衡量算法在运行过程中临时占用存储空间大小的一个量度它和时间复杂度一样是用来评价算法效率的一个重要指标。空间复杂度不仅包括在算法执行过程中输入和输出所占据的空间还包括算法执行过程中临时占用的额外空间。 空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。
注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
举例如下
例九 计算BubbleSort的空间复杂度
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;}
}BubbleSort的空间复杂度计算主要依据算法在执行过程中所需的额外内存空间。在讨论空间复杂度时我们关注的是除了输入数据本身占用的空间外算法运行时所需的附加空间。这通常包括栈空间用于存储函数调用和局部变量和堆空间用于动态内存分配。然而在冒泡排序的实现中我们主要关注的是栈空间的使用。 让我们逐一查看 BubbleSort 函数中的元素
局部变量 end: 用于标记数组中尚未排序部分的末尾。exchange: 用于标记在一次遍历中是否发生了交换以此判断数组是否已经排序完成。i: 循环计数器用于遍历数组中的元素。 参数: a: 指向数组的指针它引用了函数外部的数组因此不增加内部空间复杂度。n: 表示数组的大小是一个整型值。 递归调用: 冒泡排序是一个迭代算法不涉及递归调用因此不会因为递归调用导致栈空间显著增加。动态分配的内存: 在此实现中没有动态分配的内存算法仅在原始数组上进行操作。
计算空间复杂度
固定大小的局部变量: end、exchange 和 i 是固定大小的整型变量它们占用的空间量与数组的大小 n 无关。无递归调用: 算法不使用递归因此不会因为递归调用而在栈上占用额外的空间。无动态内存分配: 算法运行过程中没有使用如 malloc, new 等动态内存分配函数因此不会在堆上占用额外的空间。
BubbleSort 函数的空间复杂度主要由固定数量的局部变量决定这意味着它的空间需求不随输入数组的大小 n 而变化。根据空间复杂度的定义我们可以得出 BubbleSort 的空间复杂度是 O(1)即常量空间复杂度。
例十计算Fibonacci的空间复杂度
long long* Fibonacci(size_t n)
{if(n0)return NULL;long long * fibArray (long long *)malloc((n1) * sizeof(long long));fibArray[0] 0;fibArray[1] 1;for (int i 2; i n ; i){fibArray[i] fibArray[i - 1] fibArray [i - 2];}return fibArray;返回斐波那契数列的前n项
}空间复杂度分析 动态内存分配: 这个函数中最重要的部分是 fibArray 的动态内存分配。分配的空间大小直接与输入 n 成正比。即 fibArray 的大小是 n1 个 long long 类型的大小。 固定大小的局部变量: i 是一个整型变量它的大小是固定的与 n 无关。
因为函数的主要内存消耗来自于与输入大小成正比的 fibArray所以 Fibonacci 函数的空间复杂度是 O(n)。这表明所需的存储空间随着输入 n 的增长而线性增长。
例十一 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
}空间复杂度分析
递归调用: 这个函数的关键在于它使用了递归调用。每一次递归调用都需要在调用栈上增加一层用于保存当前调用的状态包括局部变量和参数。 递归深度: 递归的深度直接与输入参数 N 相关。对于每个大于 0 的 N都会产生一个递归调用直到 N 降至 0。
由于递归调用会造成调用栈大小随 N 线性增长因此 Fac 函数的空间复杂度是 O(N)。这意味着随着 N 的增大函数的内存占用也以线性方式增加。 第一节知识点大概到此结束后续我们会根据遇见的题再进行分析感谢大家的阅读
