低多边形生成网站,wordpress导入ppt,便宜的手机网站建设,qq是哪个公司开发的软件常见的时间复杂度
计算方法1、确定输入规模#xff1a;
输入规模通常用 n 表示#xff0c;例如数组长度、链表长度等。2、分析算法的执行步骤#xff1a;
计算每个操作的执行次数。
确定操作的执行次数与输入规模的关系。3、忽略常数和低阶项#xff1a;
在大O表示法中
输入规模通常用 n 表示例如数组长度、链表长度等。2、分析算法的执行步骤
计算每个操作的执行次数。
确定操作的执行次数与输入规模的关系。3、忽略常数和低阶项
在大O表示法中常数和低阶项可以忽略只保留最高阶项。
例如O(3n² 2n 1) 简化为 O(n²)。
举例
假设有一个算法其执行步骤如下arr [1, 2, 3, 4, 5]
for i in arr: # O(n)for j in arr: # O(n)print(i, j)外层循环执行 n 次。
内层循环每次外层循环执行 n 次。
总执行次数n * n n²。
时间复杂度O(n²)。 O(1)常数时间复杂度 不论输入规模如何算法的执行时间是固定的。 示例访问数组的某个元素。 arr [1, 2, 3]
print(arr[1]) # 时间复杂度为 O(1) O(n)线性时间复杂度 算法的执行时间与输入规模成正比。 示例遍历一个数组。 arr [1, 2, 3, 4, 5]
for i in arr:print(i) # 时间复杂度为 O(n) O(n²)二次时间复杂度 算法的执行时间与输入规模的平方成正比。 示例嵌套循环。 arr [1, 2, 3, 4, 5]
for i in arr:for j in arr:print(i, j) # 时间复杂度为 O(n²) O(log n)对数时间复杂度 算法的执行时间与输入规模的对数成正比。 示例二分查找。 def binary_search(arr, target):left, right 0, len(arr) - 1while left right:mid (left right) // 2if arr[mid] target:return midelif arr[mid] target:left mid 1else:right mid - 1return -1 # 时间复杂度为 O(log n) O(n log n)线性对数时间复杂度 算法的执行时间与输入规模的对数成正比。 示例快速排序、归并排序。 def merge_sort(arr):if len(arr) 1:return arrmid len(arr) // 2left merge_sort(arr[:mid])right merge_sort(arr[mid:])return merge(left, right) # 时间复杂度为 O(n log n) 空间复杂度
定义空间复杂度是指算法在运行过程中消耗的内存资源量级通常用输入规模如数组长度、链表长度等来表示。
表示方法空间复杂度也用大O符号O表示例如 O(1)、O(n)、O(n²) 等。
计算方法1确定输入规模
输入规模通常用 n 表示例如数组长度、链表长度等。2分析算法使用的额外内存
计算算法中使用的额外空间如变量、数组、递归栈等。
确定额外空间的使用量与输入规模的关系。3忽略常数和低阶项
在大O表示法中常数和低阶项可以忽略只保留最高阶项。
例如O(3n² 2n 1) 简化为 O(n²)。 假设有一个算法其执行步骤如下
Python复制
def merge_sort(arr):if len(arr) 1:return arrmid len(arr) // 2left merge_sort(arr[:mid]) # 创建左半部分数组right merge_sort(arr[mid:]) # 创建右半部分数组return merge(left, right) # 合并两个数组 递归调用每次递归调用会创建两个子数组。 空间复杂度 每次递归调用创建的子数组占用 O(n) 的空间。 递归深度为 O(log n)。 总空间复杂度为 O(n)递归栈空间。
常见的空间复杂度 O(1)常数空间复杂度 不论输入规模如何算法使用的额外内存是固定的。 示例交换两个变量的值。 a, b 1, 2
a, b b, a # 空间复杂度为 O(1) O(n)线性空间复杂度 算法使用的额外内存量与输入规模成正比。 示例复制一个数组。 arr [1, 2, 3, 4, 5]
new_arr arr[:] # 空间复杂度为 O(n) O(n²)二次空间复杂度 算法使用的额外内存量与输入规模的平方成正比。 示例创建一个二维数组。 arr [[0] * n for _ in range(n)] # 空间复杂度为 O(n²)
