gpt4 book ai didi

algorithm - 为什么 Merge 排序空间复杂度为 O(n)?

转载 作者:行者123 更新时间:2023-12-05 08:49:40 26 4
gpt4 key购买 nike

<分区>


乍一看,合并排序的空间复杂度为 O(n) 是有道理的,因为要对未排序的数组进行排序,我要拆分并创建子数组,但所有子数组的大小之和将为 n。

问题:我主要担心的是递归期间 mergerSort() 函数的内存分配问题。我有一个主堆栈,每个对 mergerSort() 的函数调用(递归地)都将被压入堆栈。现在每个递归调用的 mergeSort() 函数都有自己的堆栈。因此,假设我们对 mergeSort() 进行了 5 次递归调用,那么主堆栈将包含 5 个函数调用,其中每个函数调用都有自己的函数堆栈。现在每个函数栈都有自己的局部变量,比如函数创建的左子数组和右子数组。因此,5 个函数堆栈中的每一个都应该在内存中有 5 个不同的子数组。那么空间不应该随着递归调用的增长而增长吗?

enter image description here

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com