今天终于来学习时间复杂度了
当分析算法的时间复杂度时,我们通常关注以下几个方面来确定算法的执行时间:
-
循环次数:循环是算法中常见的结构,它会重复执行一段代码。时间复杂度取决于循环的次数。例如,一个循环从1到n的遍历,时间复杂度就是O(n)。
-
嵌套循环:如果算法中存在多个嵌套循环,我们需要考虑每个循环的迭代次数。例如,一个包含两个嵌套循环的算法,外层循环迭代n次,内层循环迭代m次,那么总的时间复杂度就是O(n * m)。
-
递归调用:递归算法通过自身的调用来解决问题。递归的时间复杂度取决于递归调用的次数以及每次递归的规模。例如,二分查找算法的时间复杂度为O(log n),其中n是输入规模。
-
条件判断和分支:条件判断语句(如if语句)的执行次数会影响算法的时间复杂度。例如,如果一个算法的执行路径取决于输入数据的特定情况,我们需要考虑每个条件判断的执行次数。
-
数据结构操作:算法中的数据结构操作,如插入、删除、查找等,对算法的时间复杂度产生影响。不同的数据结构具有不同的操作复杂度。例如,在一个数组中查找特定元素的时间复杂度为O(n),而在一个二叉搜索树中查找的时间复杂度为O(log n)。
说实话 感觉不好去理解
下面我将会从几个例子去理解
一个常见的例子是计算数组中所有元素的和。假设有一个包含n个整数的数组,我们的目标是计算出这些整数的总和。
下面我将展示两种算法的例子,并解释它们的时间复杂度。
- 算法一:迭代求和
int sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; }
这个算法使用一个循环遍历数组中的每个元素,并将它们相加得到最终的总和。在这种情况下,循环的次数与数组的大小n相等,因此循环的时间复杂度是O(n)。这是一种线性时间复杂度。
- 算法二:递归求和
int sumArray(int arr[], int start, int end) { if (start == end) { return arr[start]; } else { int mid = (start + end) / 2; int leftSum = sumArray(arr, start, mid); int rightSum = sumArray(arr, mid + 1, end); return leftSum + rightSum; } } int sum = sumArray(arr, 0, n - 1);
这个算法使用递归来分治地计算数组的总和。它将数组划分为两半,并递归地计算每个子数组的总和,然后将它们相加得到最终结果。在这个算法中,每次递归调用都将数组的规模减半,因此递归的时间复杂度是O(log n)。这是一种对数时间复杂度。
通过比较这两个算法,我们可以看到第一个算法具有线性时间复杂度O(n),而第二个算法具有对数时间复杂度O(log n)。因此,第二个算法在处理大型输入时比第一个算法更高效。
下一个例子是
二分查找:假设有一个已排序的数组,我们要在其中查找特定的元素。二分查找是一种高效的算法,其时间复杂度为O(log n)。
int binarySearch(int arr[], int target, int left, int right) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }
在每次迭代中,二分查找将搜索范围减半,直到找到目标元素或确定目标元素不存在。因此,它的时间复杂度为O(log n),其中n是数组的大小。
冒泡排序:冒泡排序是一种简单但效率较低的排序算法。它的时间复杂度为O(n^2)。
void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { // 交换相邻元素 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
冒泡排序通过多次遍历数组,比较相邻元素并交换它们的位置来实现排序。在最坏的情况下,每个元素都需要与其他元素比较和交换,因此它的时间复杂度为O(n^2)。
标签:arr,递归,int,复杂度,c++,算法,数组,day From: https://www.cnblogs.com/jszs0013/p/17549003.html