10,000 Hours

二叉树旋转重构定理 核心定理 O(n)O(n)O(n) 次旋转可以将一棵二叉树转换为任何其他具有相同遍历顺序的二叉树 定理证明 证明思路：双向构造法 步骤1：任意树 → 规范右链（Canonical Chain） 12345678910def to_canonical_chain(tree): """将任意二叉树转换为右链结构""" rotations = 0 while tree 不是右链: # 找到中序遍历中最后可能的右旋转位置 node = find_last_rotatable_node(tree) if node 存在左子树: tree = right_rotate(node) # 执行右旋转 rotations += 1 return tree, rotations 关键观察： 每次右旋转使中序遍历最后一个节点的深度增加 1 最终链中最后一个节点深度 = n−1n - 1n−1 因此最多需要 n...

Sorting学习笔记 Start 相比Array， Sorted Array在寻找数组元素上有优势，时间复杂度来到了O(logn)O(log n)O(logn) (find_max, find_min达到了O(1)O(1)O(1) ), 接下来介绍几种sort的方法 Permutation Sort 暴力枚举法，通过检查数组每一个排列方式是否已经是sorted来得到sorted Array， 时间复杂度达到了O(n!⋅n)O(n! \cdot n)O(n!⋅n) ，对于 n!n!n! 是排列的种类，这里不再过多赘述 Selection Sort 基本思路 找到最大：在当前子数组 A[0:i+1] 中找到最大元素的索引 交换位置：将最大元素交换到当前子数组的末尾 A[i] 递归排序：对剩余的子数组 A[0:i] 递归进行排序 代码实现 1234567891011121314151617def selection_sort(A, i = None): # T(i) '''Sort A[:i + 1]''' ...

我是10,000 Hours,这里是我的博客，将在这里分享我的一些学习笔记以及心得，希望大家多多支持 这是我的b站个人主页 这是一个无畏契约视频放置