社区讨论

【非魔怔】关于我口胡的排序算法

HHisaishi_Kanade
学术版参与者 9已保存回复 15

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
15 条
当前快照
1 份
快照标识符
@lo8beq5j
此快照首次捕获于
2023/10/27 15:51
2 年前
此快照最后确认于
2023/10/27 15:51
2 年前
查看原帖
今天买完蜜雪冰城，我一边喝着柠檬水一边思考这篇博客接下来怎么写。
突然我口胡了一种基于归并的排序（以结果升序为例）：
  1. O(n)O(n) 扫一遍，对于连续的上升子串，记录左右端点；连续的下降子串，翻转后记录左右端点。显然这一步应该是 O(n)O(n) 的。
  2. 对着些区间进行合并。这一步的复杂度我算不出来。已经被你爱我我爱你洗脑了
求复杂度证明。

回复

共 15 条回复，欢迎继续交流。

正在加载回复...