时间复杂度和空间复杂度的概念
在计算机算法中，时间复杂度和空间复杂度是衡量算法性能的两个重要指标。
时间复杂度是指算法执行所需的时间，通常用算法基本操作执行次数的数量级来表示，用O()表示（大O符号），称为“大O记法”。
空间复杂度是指算法执行所需的存储空间，包括代码本身所占据的存储空间以及程序执行时所需的临时空间。空间复杂度通常也用O()表示，表示存储单元的数量级。
时间复杂度的示例
以下是几种常见的时间复杂度：
- O(1)表示执行时间是常数级的算法，无论输入数据的规模大小为多少，算法的执行时间都相同，如简单的赋值操作。
def assign_value(a):
a = 10 # 常量级别的操作
return a- O(n)表示执行时间和输入数据中的元素数量成正比，如顺序搜索。
def linear_search(lst, x):
for i in range(len(lst)):
if lst[i] == x:
return i
return -1- O(n^2)表示执行时间和输入数据中的元素数量平方成正比，如排序中的冒泡排序。
def bubble_sort(lst):
n = len(lst)
for i in range(n):
for j in range(n-i-1):
if lst[j] > lst[j+1]:
lst[j], lst[j+1] = lst[j+1], lst[j]
return lst- O(log n)表示执行时间和输入数据中的元素数量的对数成正比，如二分查找。
def binary_search(lst, x):
low, high = 0, len(lst)-1
while low <= high:
mid = (low+high) // 2
if lst[mid] == x:
return mid
elif lst[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1- O(n log n)表示执行时间和输入数据中的元素数量和对数的乘积成正比，如排序中的归并排序。
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left_lst = merge_sort(lst[:mid])
right_lst = merge_sort(lst[mid:])
i, j = 0, 0
result = []
while i < len(left_lst) and j < len(right_lst):
if left_lst[i] < right_lst[j]:
result.append(left_lst[i])
i += 1
else:
result.append(right_lst[j])
j += 1
result += left_lst[i:]
result += right_lst[j:]
return result空间复杂度的示例
以下是几种常见的空间复杂度：
- O(1)表示算法所需的存储空间是常数级别的，如递归的斐波那契数列。
def fib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a+b
return a- O(n)表示算法所需的存储空间和输入数据的规模成正比，如顺序搜索。
def linear_search(lst, x):
for i in range(len(lst)):
if lst[i] == x:
return i
return -1- O(n^2)表示算法所需的存储空间和输入数据的规模平方成正比，如排序中的冒泡排序。
def bubble_sort(lst):
n = len(lst)
for i in range(n):
for j in range(n-i-1):
if lst[j] > lst[j+1]:
lst[j], lst[j+1] = lst[j+1], lst[j]
return lst- O(log n)表示算法所需的存储空间和输入数据的规模的对数成正比，如递归的二分查找。
def binary_search(lst, x, low, high):
if low > high:
return -1
mid = (low+high) // 2
if lst[mid] == x:
return mid
elif lst[mid] < x:
return binary_search(lst, x, mid+1, high)
else:
return binary_search(lst, x, low, mid-1)- O(n log n)表示算法所需的存储空间和输入数据的规模和对数的乘积成正比，如排序中的归并排序。
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left_lst = merge_sort(lst[:mid])
right_lst = merge_sort(lst[mid:])
i, j = 0, 0
result = []
while i < len(left_lst) and j < len(right_lst):
if left_lst[i] < right_lst[j]:
result.append(left_lst[i])
i += 1
else:
result.append(right_lst[j])
j += 1
result += left_lst[i:]
result += right_lst[j:]
return result
