在线音乐网站 用什么做,青海h5页面制作,班级网站建设维护,不会被禁止访问的浏览器前言
在算法的世界里#xff0c;效率是衡量算法优劣的关键标准。今天#xff0c;就让我们深入探讨算法效率的两个核心维度#xff1a;时间复杂度和空间复杂度#xff0c;帮助你在算法设计的道路上更进一步。
一、算法效率#xff1a;衡量算法好坏的关键
算法的效率主要…前言
在算法的世界里效率是衡量算法优劣的关键标准。今天就让我们深入探讨算法效率的两个核心维度时间复杂度和空间复杂度帮助你在算法设计的道路上更进一步。
一、算法效率衡量算法好坏的关键
算法的效率主要体现在两个方面时间和空间。时间复杂度衡量的是算法运行的快慢而空间复杂度则衡量算法运行所需的额外空间。在计算机发展的早期存储容量有限空间复杂度备受关注。然而随着计算机存储容量的飞速发展如今我们更关注算法的时间复杂度。
1.1 斐波那契数列一个经典的例子
斐波那契数列是一个经典的算法问题。其递归实现方式简洁明了但这种简洁性是否意味着它是一个好的算法呢答案并非绝对。递归实现虽然代码简洁但其时间复杂度较高对于较大的输入值运行时间会显著增加。这正是我们需要深入分析算法复杂度的原因。
long long Fib(int N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}二、时间复杂度算法运行快慢的量化
时间复杂度是衡量算法运行时间的函数。它通过分析算法中基本操作的执行次数来确定。在实际中我们通常使用大O的渐进表示法来简化复杂度的表达。
2.1 大O的渐进表示法
大O符号Big O notation是描述函数渐进行为的数学符号。推导大O阶的方法如下 用常数1取代运行时间中的所有加法常数。 在修改后的运行次数函数中只保留最高阶项。 如果最高阶项存在且不是1则去除与这个项目相乘的常数。 例如对于以下代码
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;}
}通过计算我们发现基本操作count的执行次数为 N^ 22*N10。使用大O的渐进表示法我们去掉常数项和低阶项得到时间复杂度为 O(N ^2 )。
2.2 常见时间复杂度计算举例
让我们通过一些实例来进一步理解时间复杂度的计算。
实例1
void Func2(int N)
{int count 0;for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}
}基本操作执行了 2N10 次时间复杂度为 O(N)。
实例2
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;}
}基本操作执行了 MN 次时间复杂度为 O(NM)。
实例3
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}
}基本操作执行了10次时间复杂度为 O(1)。O1不是代表一次而是代表常数次
实例4
const char *strchr(const char *str, int character);while(*str)
{if(*str character)return str;str;时间复杂度为 O(N)。(一般以最坏情况作为时间复杂度
实例5
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;}
}时间复杂度为 O(N^2 )。最好ON最坏ON ^ 2)
实例6有序 经典二分查找
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 mid 1;else if (a[mid] x)end mid;elsereturn mid;}return -1;
}时间复杂度为 O(logN)。最好O1最坏OlogN区间缩放到一个值时要么找到要么找不到折半查找多少次x就除多少个2。2^xN
三、空间复杂度算法所需额外空间的量化
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。它主要通过函数在运行时显式申请的额外空间来确定。
3.1 空间复杂度计算实例
实例1
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}Fac(N)
Fac(N-1)
Fac(N-2)
...
Fac(1)
Fac(0)空间复杂度为 O(N)。
实例2
long long *Fibonacci(size_t n)
{if (n 0)return NULL;long long *fibArray (long long *)malloc((n 1) * 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;
}空间复杂度为 O(N)。
实例3
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}2^0 Fib(N)2^1Fib(N-1) Fib(N-2)2^2 Fib(N-2) Fib(N-3) Fib(N-3) Fib(N-2)...2^(N-1)Fib(2) Fib(1)空间复杂度为 O(2^N)。
四、常见复杂度对比
常见的复杂度从低到高依次为O(1)、O(logN)、O(N)、O(NlogN)、O(N^2 )、O(2 ^N )、O(N!)。选择合适的算法可以显著提升程序的运行效率。
五、复杂度的OJ练习
理论学习之后通过实践来巩固知识是必不可少的。以下是一些推荐的OJ题目 消失的数字 参考 1. 2.
旋转数组
总结
时间复杂度和空间复杂度是算法设计中不可或缺的两个维度。通过深入理解它们我们可以更好地选择和设计高效的算法。希望这篇文章能帮助你更好地掌握算法效率的分析方法让你在算法学习的道路上更进一步。
