时间复杂度和空间复杂度

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

在计算机科学中，时间复杂度（Time Complexity）和空间复杂度（Space Complexity）是两个重要的概念，它们描述了算法或程序执行过程中的性能。

### 时间复杂度时间复杂度是指一个算法或程序执行所需的时间量，与输入规模相关。它通常用大O符号表示，例如O(n)、O(log n)等。时间复杂度反映了算法或程序在不同输入规模下执行速度的变化。

**常见时间复杂度**

* O(1)：恒定时间复杂度，表示算法或程序执行所需的时间量不随输入规模而改变。
* O(log n)：对数时间复杂度，表示算法或程序执行所需的时间量与输入规模的对数成正比。
* O(n)：线性时间复杂度，表示算法或程序执行所需的时间量与输入规模成正比。
* O(n log n)：线性对数时间复杂度，表示算法或程序执行所需的时间量与输入规模的乘积成正比。
* O(n^2)：平方时间复杂度，表示算法或程序执行所需的时间量与输入规模的平方成正比。

### 空间复杂度空间复杂度是指一个算法或程序使用的存储空间量，与输入规模相关。它通常用大O符号表示，例如O(n)、O(log n)等。空间复杂度反映了算法或程序在不同输入规模下占用的存储空间的变化。

**常见空间复杂度**

* O(1)：恒定空间复杂度，表示算法或程序使用的存储空间量不随输入规模而改变。
* O(log n)：对数空间复杂度，表示算法或程序使用的存储空间量与输入规模的对数成正比。
* O(n)：线性空间复杂度，表示算法或程序使用的存储空间量与输入规模成正比。

###例子#### 时间复杂度示例

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

arr = [3,6,8,10,1,4,7]
print(quick_sort(arr))

def bubble_sort(arr):
 for i in range(len(arr)):
 for j in range(len(arr) -1):
 if arr[j] > arr[j +1]:
 arr[j], arr[j +1] = arr[j +1], arr[j]
 return arrarr = [3,6,8,10,1,4,7]
print(bubble_sort(arr))