目录
简介
时间复杂度
大O复杂度表示法
空间复杂度
前言-与正文无关
生活远不止眼前的苦劳与奔波,它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界中,我们往往容易陷入工作的漩涡,忘记了停下脚步,感受周围的世界。让我们一起提醒自己,要适时放慢脚步,欣赏生活中的每一道风景,享受与家人朋友的温馨时光,发现那些平凡日子里隐藏的幸福时刻。因为,这些点点滴滴汇聚起来的,才是构成我们丰富多彩生活的本质。希望每个人都能在繁忙的生活中找到自己的快乐之源,不仅仅为了生存而工作,更为了更好的生活而生活。
送你张美图!希望你开心!
简介
数据结构和算法本质上是”快“和"省"。所以代码的执行效率是非常重要的度量,我们采用时间复杂度和空间复杂度来计算
时间复杂度
大O复杂度表示法
大O符号(Big O notation)是一种数学符号,用于描述算法的时间复杂度,即算法执行所需时间与输入数据大小之间的关系。O
代表了“Order of”(阶),它后面跟着的是一个函数,这个函数表示了算法复杂度随输入大小增加的增长率。
我们经常可以在各种数据结构看到,O(n)、O(logn)之类的数据,但往往却不知道其意,下面我给介绍一下吧。
-
O(1) - 常数时间复杂度: 无论数据量如何,算法所需时间都是固定的。例如,访问数组中的元素长度,长度length早就被存起来了随时可以取长度是多少。
-
O(n) - 线性时间复杂度: 算法执行时间与输入数据的大小成正比。例如,遍历数组或链表。
如下面代码,每行代码执行时间为t,当你入参为n时,for循环就是t*n,T(n):代表代码执行时间。总时间就是T(n)=3t+2tn。当n无限大时,低阶、常量、系数都可以忽略,当然你可以看到决定你代码核心时间因素不是t,因为t是固定的,那么你忽略下3t 和 t和2,也就是n ,即上例中的时间复杂度为O(n),也就是代码执行时间随着数据规模的增加而增长
int sum(int n){
int s=0; //t
int i=1; //t
for(;i<=n;i++){ //t*n
s=s+i; //t*n
}
return s; //t
}
-
O(log n) - 对数时间复杂度: 随着输入数据的增加,所需时间的增长速度会逐渐减慢。二分查找就是一个典型的 O(log n) 算法。(相对于O(n),如果你的算法是这个,那么就代表他很完美)
下述是个二分查找法,可以看到通过算法将数据查询复杂度减半
public class BinarySearch {
public static int binarySearch(int[] array, int value) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // 防止溢出的写法
int midVal = array[mid];
if (midVal < value) {
low = mid + 1;
} else if (midVal > value) {
high = mid - 1;
} else {
return mid; // 找到元素,返回其索引
}
}
return -1; // 元素未找到
}
public static void main(String[] args) {
int[] arr = {-22, -15, 1, 7, 20, 35, 55}; // 假定数组已排序
int searchValue = 20;
int resultIndex = binarySearch(arr, searchValue);
if (resultIndex >= 0) {
System.out.println("在索引处找到的元素: " + resultIndex);
} else {
System.out.println("在数组中找不到元素.");
}
}
}
-
O(n log n) - 线性对数时间复杂度: 这通常出现在执行了 O(log n) 复杂度的操作 n 次,如快速排序和归并排序。
-
O(n^2) - 平方时间复杂度: 时间复杂度与输入数据的平方成正比。例如,两层嵌套循环。n^2就是n的2次方,下面其他例子看到^,也可以这么理解!
int sum(int n){
int s=0;
int i=1;
int j=1;
for(;i<=n;i++){// n
j=1;
for(;j<=m;j++){ //n*m
s=s+i+j; //n*m
}
}
return s;
}
-
O(2^n) - 指数时间复杂度: 算法的运行时间随输入大小呈指数增长。很多递归算法(如计算斐波那契数列的简单实现)具有这样的时间复杂度。
-
O(n!) - 阶乘时间复杂度: 算法的运行时间与输入数据的阶乘成正比,这通常出现在解决排列问题时
空间复杂度
------------------------------------------与正文内容无关------------------------------------
如果觉的文章写对各位读者老爷们有帮助的话,麻烦点赞加关注呗!作者在这拜谢了!
混口饭吃了!如果你需要Java 、Python毕设、商务合作、技术交流、就业指导、技术支持度过试用期。请在关注私信我,本人看到一定马上回复!
这是我全部文章所在目录,看看是否有你需要的,如果遇到觉得不对地方请留言,看到后我会查阅进行改正。
A乐神-CSDN博客