【数据结构和算法】-时间复杂度

时间复杂度概述

时间复杂度是衡量算法执行效率的一个重要指标，它描述了算法运行时间与输入数据规模之间的关系。时间复杂度通常用大O表示法（Big O notation）来表示。

常见的时间复杂度

O(1) - 常数时间复杂度
- 描述：无论输入数据规模如何，算法的执行时间都是常数。
- 示例：访问数组中的某个元素。
```
int[] array = {1, 2, 3, 4, 5};
int element = array[3]; // O(1)
```

O(log n) - 对数时间复杂度

描述：算法的执行时间与输入数据规模的对数成正比。

示例：二分查找。

int binarySearch(int[] array, int target) {int left = 0, right = array.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (array[mid] == target) return mid;else if (array[mid] < target) left = mid + 1;else right = mid - 1;}return -1; // O(log n)
}

O(n) - 线性时间复杂度
- 描述：算法的执行时间与输入数据规模成线性关系。
- 示例：遍历数组。
```
int sum = 0;
for (int i = 0; i < array.length; i++) {sum += array[i]; // O(n)
}
```

O(n log n) - 线性对数时间复杂度

描述：算法的执行时间与输入数据规模的对数成线性关系。

示例：归并排序。

void mergeSort(int[] array, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(array, left, mid);mergeSort(array, mid + 1, right);merge(array, left, mid, right); // O(n log n)}
}

O(n^2) - 平方时间复杂度

描述：算法的执行时间与输入数据规模的平方成正比。

示例：冒泡排序。

void bubbleSort(int[] array) {for (int i = 0; i < array.length - 1; i++) {for (int j = 0; j < array.length - 1 - i; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp; // O(n^2)}}}
}

O(2^n) - 指数时间复杂度
- 描述：算法的执行时间与输入数据规模的指数成正比。
- 示例：递归计算斐波那契数列。
```
int fibonacci(int n) {if (n <= 1) return n;return fibonacci(n - 1) + fibonacci(n - 2); // O(2^n)
}
```

O(n!) - 阶乘时间复杂度

描述：算法的执行时间与输入数据规模的阶乘成正比。

示例：生成所有排列组合。

void permute(int[] nums, int start, List<List<Integer>> result) {if (start == nums.length) {result.add(new ArrayList<>(Arrays.asList(nums)));} else {for (int i = start; i < nums.length; i++) {swap(nums, start, i);permute(nums, start + 1, result);swap(nums, start, i); // O(n!)}}
}void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;
}