保定市做网站公司地址电话,广告设计和平面设计有什么区别,wordpress 调用豆瓣,公关公司属于什么行业时间和空间复杂度 【本节目标】1. 如何衡量一个算法的好坏2. 算法效率3. 时间复杂度3.1 时间复杂度的概念3.2 大O的渐进表示法3.3 推导大O阶方法3.4 常见时间复杂度计算举例3.4.1 示例13.4.2 示例23.4.3 示例33.4.4 示例43.4.5 示例53.4.6 示例63.4.7 示例7 4.空间复杂度4.1 示… 时间和空间复杂度 【本节目标】1. 如何衡量一个算法的好坏2. 算法效率3. 时间复杂度3.1 时间复杂度的概念3.2 大O的渐进表示法3.3 推导大O阶方法3.4 常见时间复杂度计算举例3.4.1 示例13.4.2 示例23.4.3 示例33.4.4 示例43.4.5 示例53.4.6 示例63.4.7 示例7 4.空间复杂度4.1 示例14.2 示例24.3 示例3 【本节目标】
算法效率时间复杂度空间复杂度
1. 如何衡量一个算法的好坏
下面求斐波那契数列的算法好还是不好为什么该如何衡量一个算法的好坏呢
public static long Fib(int N) {if (N 3) {return 1;}return Fib(N - 1) Fib(N - 2);
}2. 算法效率
算法效率分析主要分为两种具体包括
时间效率也被称为时间复杂度。它主要衡量算法中基本操作的执行次数。在计算时间复杂度时通常使用大O的渐进表示法。时间复杂度是评估算法运行速度快慢的重要指标常见的时间复杂度包括O(1)、O(logn)、O(n)、O(n^2)等。随着问题规模的扩大时间效率的重要性愈发突出因为它直接影响到算法处理大数据集的能力。空间效率也被称为空间复杂度。它主要是对算法在运行中临时占用的空间大小的度量。换句话说它计算了算法在运行过程中开辟了多少额外的空间例如数组的大小。如果算法没有开辟新的数组则其空间复杂度为O(1)若开辟了N个数组则为O(N)。对于递归调用空间复杂度取决于递归的深度或次数。虽然在现代计算机硬件环境中内存空间越来越大对空间效率的考虑可能相对较少但优化空间使用仍然是一个好的编程实践特别是在处理大规模数据或资源受限的环境中。
3. 时间复杂度
3.1 时间复杂度的概念
时间复杂度的定义在计算机科学中算法的时间复杂度是一个数学函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。
3.2 大O的渐进表示法
// 请计算一下func1基本操作执行了多少次
public static 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--) 0) {count;}System.out.println(count);
}Func1 执行的基本操作次数 N 10 F(N) 130N 100 F(N) 10210N 1000 F(N) 1002010
实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。
大O符号Big O notation是用于描述函数渐进行为的数学符号。
3.3 推导大O阶方法
用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后Func1的时间复杂度为 N 10 F(N) 100N 100 F(N) 10000N 1000 F(N) 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况:
最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界)
例如在一个长度为N数组中搜索一个数据x
最好情况1次找到 最坏情况N次找到 平均情况N/2次找到
在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N)
3.4 常见时间复杂度计算举例
3.4.1 示例1
// 计算func2的时间复杂度
void func2(int N) {int count 0;for (int k 0; k 2 * N; k) {count;}int M 10;while ((M--) 0) {count;}System.out.println(count);
}首先我们分析func2函数中的各个部分 有一个for循环其循环次数为2 * N。在这个循环中count每次递增1因此这部分的时间复杂度是O(N)。 紧接着有一个while循环其循环次数固定为10次因为M被初始化为10并且在每次循环中递减直到为0。在这部分count也每次递增1但这部分的时间复杂度是常数时间即O(1)因为它不依赖于输入N。 最后有一个输出语句System.out.println(count);这也是常数时间操作即O(1)。
综上所述虽然函数中有两个循环但第二个循环的时间复杂度是常数不随N的变化而变化。因此整个函数func2的时间复杂度主要由第一个for循环决定即O(N)。
所以func2的时间复杂度是O(N)。
3.4.2 示例2
// 计算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;}System.out.println(count);
}在func3函数中我们有两个for循环 第一个for循环的次数由参数M决定循环体内执行的操作是count这是一个常数时间操作。因此第一个循环的时间复杂度是O(M)。 第二个for循环的次数由参数N决定同样地循环体内执行的操作也是count这也是一个常数时间操作。因此第二个循环的时间复杂度是O(N)。 最后有一个输出语句System.out.println(count);这是常数时间操作即O(1)。
综合考虑两个循环它们各自独立且没有嵌套关系所以整个函数的时间复杂度是两个循环时间复杂度的和即O(M N)。
因此func3的时间复杂度是O(M N)。这意味着函数执行所需的时间与M和N的线性之和成正比。
3.4.3 示例3
// 计算func4的时间复杂度
void func4(int N) {int count 0;for (int k 0; k 100; k) {count;}System.out.println(count);
}在func4函数中我们有一个for循环和一个输出语句 for循环的次数是固定的为100次因为循环条件是k 100。在循环体内执行的操作是count这是一个常数时间操作。由于循环次数不依赖于输入N因此这部分的时间复杂度是常数时间即O(1)。这里需要注意的是尽管循环执行了100次但时间复杂度仍然看作是常数时间因为无论N的值是多少这个循环的次数都不会改变。 输出语句System.out.println(count);也是常数时间操作即O(1)。
综合考虑上述两部分整个函数func4的时间复杂度是常数时间即O(1)。这意味着无论输入N的大小如何函数执行所需的时间都是固定的。
因此func4的时间复杂度是O(1)。
3.4.4 示例4
// 计算bubbleSort的时间复杂度
void bubbleSort(int[] array) {for (int end array.length; end 0; end--) {boolean sorted true;for (int i 1; i end; i) {if (array[i - 1] array[i]) {Swap(array, i - 1, i);sorted false;}}if (sorted true) {break;}}
}private void Swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;
}冒泡排序Bubble Sort的时间复杂度分析如下
在最坏的情况下即数组完全逆序时冒泡排序需要进行n-1轮比较和交换n是数组的长度。在每一轮中冒泡排序会从数组的开始比较相邻的元素并且根据需要交换它们直到到达当前轮的结束位置。这个过程会重复进行直到整个数组排序完成。
对于每一轮我们需要进行end-1次比较end是当前轮需要考虑的数组长度它随着每一轮的递减而减少。因此如果我们计算所有轮中的比较次数我们会发现它是一个等差数列的和首项为n-1末项为1项数为n-1。等差数列的和公式为S n/2 * (首项 末项) * 项数代入得S (n-1)/2 * (n-1 1) * (n-1) (n-1)^2 * (n/2)。由于我们只关心最高次项来确定时间复杂度因此可以简化为O(n^2)。
另外考虑到最好情况下即数组已经排好序时冒泡排序可能在第一轮就终止因为sorted标志会在第一轮后被设置为true从而跳出外层循环。这种情况下时间复杂度为O(n)。但是由于我们通常在分析算法复杂度时考虑的是最坏情况所以冒泡排序的时间复杂度通常被认为是O(n^2)。
综上所述冒泡排序的时间复杂度是O(n^2)。
此外值得注意的是空间复杂度是O(1)因为冒泡排序是原地排序算法不需要额外的存储空间。
Swap函数的时间复杂度是O(1)因为它只执行了固定数量的操作不依赖于输入数组的大小。因此在分析冒泡排序的整体时间复杂度时Swap函数的开销可以被忽略。
3.4.5 示例5
// 计算binarySearch的时间复杂度
int binarySearch(int[] array, int value) {int begin 0;int end array.length - 1;while (begin end) {int mid begin ((end - begin) / 2);if (array[mid] value)begin mid 1;else if (array[mid] value)end mid - 1;elsereturn mid;}return -1;
}二分查找Binary Search算法的时间复杂度分析如下
二分查找是一种在有序数组中查找特定元素的算法。在每次迭代中算法都会将搜索范围减半通过比较中间元素与目标值来决定接下来在数组的哪一半中继续搜索。
在最坏的情况下即目标值不存在于数组中或者存在于数组的最末端二分查找需要进行log2(n)次迭代这里的n是数组的长度。这是因为每次迭代都会将搜索范围减半所以需要迭代的次数与数组的长度成对数关系。
因此二分查找的时间复杂度是O(log n)这里的n代表数组的长度。这意味着无论数组有多大二分查找所需的迭代次数都相对较少使得它成为一种非常高效的查找算法尤其是在处理大规模数据集时。
综上所述binarySearch函数的时间复杂度是O(log n)。这里的log是以2为底的对数但在复杂度分析中我们通常省略底数因为对于不同的底数复杂度仍然是相同的数量级。
另外值得注意的是二分查找的空间复杂度是O(1)因为它只需要常数级别的额外空间来存储begin、end和mid等变量。
3.4.6 示例6
// 计算阶乘递归factorial的时间复杂度
long factorial(int N) {return N 2 ? N : factorial(N - 1) * N;
}阶乘递归函数 factorial 的时间复杂度分析如下
递归函数的时间复杂度通常通过分析递归树或递归调用的次数来确定。在这个阶乘函数中每次递归调用都会使 N 减少 1直到 N 变为 1 或 0。因此递归的深度即递归调用的次数与输入 N 成正比。
对于给定的输入 N函数会进行 N 次递归调用包括初始调用。在每次递归调用中除了递归调用自身外还执行了一次乘法操作。由于乘法操作的时间复杂度是常数时间 O(1)因此总的时间复杂度主要取决于递归调用的次数。
所以阶乘递归函数 factorial 的时间复杂度是 O(N)其中 N 是输入参数。这意味着函数执行所需的时间与 N 成线性关系。
另外值得注意的是虽然这个函数的时间复杂度是线性的但当 N 很大时递归可能会导致栈溢出或超出 long 类型的最大值。因此在实际应用中可能需要考虑使用迭代版本的阶乘函数或者使用大数库来处理大数阶乘。
3.4.7 示例7
// 计算斐波那契递归fibonacci的时间复杂度
int fibonacci(int N) {return N 2 ? N : fibonacci(N - 1) fibonacci(N - 2);
}斐波那契递归函数 fibonacci 的时间复杂度分析稍微复杂一些因为它涉及到大量的重复计算。我们来详细分析一下
这个函数使用递归方式计算斐波那契数列的第 N 项其中 N 是输入参数。斐波那契数列是这样一个序列0, 1, 1, 2, 3, 5, 8, 13, …其中每个数是前两个数的和。
在递归函数中为了计算 fibonacci(N)需要计算 fibonacci(N-1) 和 fibonacci(N-2)。然而这两个递归调用又会进一步引发更多的递归调用而且很多计算是重复的。例如在计算 fibonacci(N) 时会计算 fibonacci(N-1)而在计算 fibonacci(N-1) 时又会再次计算 fibonacci(N-2)这个 fibonacci(N-2) 在计算 fibonacci(N) 时已经被计算过一次了。
这种重复计算会导致函数的时间复杂度非常高。实际上这个递归函数的时间复杂度是指数级的具体来说是 O(2^N)其中 N 是输入参数。这是因为对于每个 N都会有两个递归调用形成一个二叉树结构的调用图其深度为 N每一层的节点数大致是上一层的两倍。
因此尽管斐波那契递归函数在概念上很简单但由于大量的重复计算它的性能非常差。在实际应用中通常会使用动态规划、迭代或其他优化方法来避免这种重复计算从而降低时间复杂度。例如可以使用一个数组来存储已经计算过的斐波那契数以便在需要时重用这些值而不是重新计算它们。这种方法可以将时间复杂度降低到 O(N)。
4.空间复杂度
4.1 示例1
// 计算bubbleSort的间空复杂度
void bubbleSort(int[] array) {for (int end array.length; end 0; end--) {boolean sorted true;for (int i 1; i end; i) {if (array[i - 1] array[i]) {Swap(array, i - 1, i);sorted false;}}if (sorted true) {break;}}
}private void Swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;
}冒泡排序Bubble Sort算法的空间复杂度分析如下
空间复杂度是指算法在运行过程中临时占用存储空间的大小。在冒泡排序算法中我们主要关注两个方面存储输入数组的空间和算法运行过程中额外使用的空间。 存储输入数组的空间这部分空间是固定的由输入数组的大小决定与算法本身无关。因此在分析算法的空间复杂度时我们通常不考虑这部分空间。 算法运行过程中额外使用的空间在冒泡排序中除了输入数组外我们只需要一些额外的变量来辅助排序过程。在你的代码中这些变量包括end、sorted、i以及Swap函数中的tmp。这些都是简单的整型变量或布尔变量它们占用的空间是常数级别的与输入数组的大小无关。
综上所述冒泡排序算法的空间复杂度是O(1)。这是因为算法在运行过程中只需要常数级别的额外空间不随输入数组的大小而变化。这意味着无论输入数组有多大冒泡排序所需的额外空间都是固定的。
4.2 示例2
// 计算斐波那契递归fibonacci的空间复杂度
int fibonacci(int N) {return N 2 ? N : fibonacci(N - 1) fibonacci(N - 2);
}斐波那契递归函数 fibonacci 的空间复杂度主要由递归调用的深度决定。由于该函数采用递归方式计算斐波那契数列每次递归调用都会将当前函数的执行上下文压入系统栈直到递归到达基准情况N 2时开始返回。
在最坏的情况下即计算 fibonacci(N) 时递归调用的深度将与 N 成正比。这是因为每个递归调用都会进一步调用 fibonacci(N-1) 和 fibonacci(N-2)形成了一棵二叉递归树。尽管存在大量的重复计算但从空间占用的角度来看我们关心的是递归树的最大深度。
递归树的最大深度大致为 N因为每次递归调用都会使 N 减小 1 或 2直到 N 变为 0 或 1。因此系统栈中需要存储的递归调用上下文数量最多为 N 个。
所以斐波那契递归函数 fibonacci 的空间复杂度是 O(N)其中 N 是输入参数。这意味着函数执行所需的最大栈空间与 N 成线性关系。在实际应用中由于递归调用的数量巨大这个函数很容易导致栈溢出特别是对于较大的 N 值。因此虽然从理论上看空间复杂度是线性的但在实践中这个函数可能会因为栈空间不足而失败。
4.3 示例3
// 计算阶乘递归factorial的空间复杂度
long factorial(int N) {return N 2 ? N : factorial(N - 1) * N;
}阶乘递归函数 factorial 的空间复杂度分析如下
该函数是一个递归函数用于计算给定整数 N 的阶乘。在递归过程中每次函数调用都会创建一个新的执行上下文该上下文需要被存储在系统栈中直到函数返回结果。
对于 factorial 函数每次递归调用都会使 N 减 1直到达到基准情况 N 2。因此递归的深度也就是递归调用的次数与 N 的值直接相关。
在最坏的情况下即当 N 是一个较大的正整数时递归调用的次数将是 N 次如果我们从 N 开始计数直到递归到基准情况。每次递归调用都会在系统栈中增加一个执行上下文因此栈的最大深度将是 N。
所以阶乘递归函数 factorial 的空间复杂度是 O(N)其中 N 是输入参数。这意味着函数执行所需的最大栈空间与 N 成线性关系。尽管每次递归调用本身不占用太多额外空间除了系统栈中的执行上下文外但由于递归的深度可能很大因此该函数在处理非常大的 N 值时可能会遇到栈溢出的问题。
