chapter_divide_and_conquer/divide_and_conquer/

[giscus[bot]]

chapter_divide_and_conquer/divide_and_conquer/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_divide_and_conquer/divide_and_conquer/

[1104797544]

1. 操作数量优化¶
   以“冒泡排序”为例，其处理一个长度为 (n) 的数组需要 (O(n^2)) 时间。假设我们按照图 12-2 所示的方式，将数组从中点分为两个子数组，则划分需要 (O(n)) 时间，排序每个子数组需要 (O((n / 2)^2)) 时间，合并两个子数组需要 (O(n)) 时间，总体时间复杂度为：

[ O(n + (\frac{n}{2})^2 \times 2 + n) = O(\frac{n^2}{2} + 2n) ]

----这里推导公式是不是多了写特殊符号？markdown解析问题吗

[krahets]

应该是网络问题，试试换个网络环境，比如手机 4G

[clearwater753]

作者您好，我想问一下为什么将数组从中点分为两个子数组，划分需要O(n)时间？
直接计算中点不是O(1)时间吗？中点计算好了也就划分好了？

[lrisora]

最后一步排序结果需要存入原位，所以这里的子数组是新申请的内存，需要整体复制
如果直接将原内存二分原地冒泡的话
接下来的合并就需要将这8个数据先整体复制出来
才能在原内存生成合并结果，这使得合并复杂度变为O(2n)
整体是一致的

[Aidener]

这个证明漂亮，比起一些支支吾吾半天讲不出所以然的舒服多了

[qw124341789]

归并排序真的是太“分治”了

[bnufw]

以“冒泡排序”为例......
这是笔误了嘛，应该是以"归并排序"为例吧？

[bnufw]

嗷嗷，懂了

[bnufw]

在1. 操作数量优化 的例子中
划分的复杂度为什么是O(n)？我的想法是，由于len()函数的复杂度为O(1),那就直接len/2
对么？

[krahets]

Hi，这里的划分是指划分为两个子数组，涉及遍历 + 赋值操作，因此时间复杂度为 O(n)

[480284856]

hello, K神，我觉得“分”阶段的把一个原数组划分为两个子数组的过程，应该是计算middle的过程吧，这里是不涉及遍历和赋值操作的，只有在“治”的阶段，才会遍历两个已排好序的子数组，并进行“两个子数组的值排序好，放到tmp数组中"以及"把tmp数组中的值放回nums"的赋值操作吧。

def merge_sort(nums: list[int], left: int, right: int):
    if left==right:
        return
    
    # 把一个长数组划分为两个子数组，分别排好序
    mid=int((left+right)/2)
    merge_sort(nums, left, med)
    merge_sort(nums, med+1, right)

    merge(nums, left, mid, right)

[480284856]

所以我感觉分治一次的冒泡排序的时间复杂度应该是 $O(2(\frac{n}{2})^2 + n)$

[480284856]

我明白了，冒泡排序函数的参数只有一个nums，所以得复制出来。

[Kore-yoshi]

我我我有一个很大的疑问，可以说递归这个思想理解起来还是比较容易，但是如何使用它，怎么能够想起来使用它好像是一个很大的问题哎。
就以leetcode的21题合并两个有序链表为例子，题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
这个题是如何想起来能够使用递归的？希望各位佬能够耐心解释一下（根本想不出来，不知道是不是自己对递归的理解有误或者是不太深）

[hpstory]

Hi @Kore-yoshi , 看看这篇，里面的例子可以加深你对递归的理解。递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。

[krahets]

递归的关键在于定义“问题及子问题之间的关系”。例如将“将两个升序链表合并为一个新的升序链表”。那么假设两个链表的长度分别为 m, n，设原问题为 f(m, n)。假设我们先合并了第一个链表的首节点，那么剩余的就是子问题 f(m-1, n) ；以此递归下去，最终达到 f(0, 0) 时问题就能得到解决。