Python算法中的时间复杂度与空间复杂度

**时间复杂度与空间复杂度**

在编程中，算法的效率是衡量其好坏的一个重要指标。两个关键概念——时间复杂度和空间复杂度—are—用于描述算法的性能。

### 时间复杂度时间复杂度（Time Complexity）是指算法执行所需的时间与输入大小的关系。它通常用大O符号表示，例如O(n)、O(log n)等。

**常见时间复杂度**

* O(1)：恒定时间复杂度，表示算法在任何情况下都只需要常数时间。
* O(log n)：对数时间复杂度，表示算法的执行时间与输入大小的对数成正比。
* O(n)：线性时间复杂度，表示算法的执行时间与输入大小成正比。
* O(n log n)：线性对数时间复杂度，表示算法的执行时间与输入大小的乘积成正比。
* O(n^2)：平方时间复杂度，表示算法的执行时间与输入大小的平方成正比。
* O(2^n)：指数时间复杂度，表示算法的执行时间与输入大小的指数成正比。

### 空间复杂度空间复杂度（Space Complexity）是指算法所需的存储空间与输入大小的关系。它也通常用大O符号表示。

**常见空间复杂度**

* O(1)：恒定空间复杂度，表示算法在任何情况下都只需要常数空间。
* O(log n)：对数空间复杂度，表示算法所需的存储空间与输入大小的对数成正比。
* O(n)：线性空间复杂度，表示算法所需的存储空间与输入大小成正比。

###例子####1. 查找最大值

def find_max(nums):
 max_num = nums[0]
 for num in nums:
 if num > max_num:
 max_num = num return max_num

def quick_sort(nums):
 if len(nums) <=1:
 return nums pivot = nums[len(nums) //2]
 left = [x for x in nums if x < pivot]
 middle = [x for x in nums if x == pivot]
 right = [x for x in nums if x > pivot]
 return quick_sort(left) + middle + quick_sort(right)

def binary_search(nums, target):
 left, right =0, len(nums) -1 while left <= right:
 mid = (left + right) //2 if nums[mid] == target:
 return mid elif nums[mid] < target:
 left = mid +1 else:
 right = mid -1 return -1