type
status
date
slug
summary
tags
category
icon
password
Last edited time
Jan 29, 2025 12:49 PM
课堂总结
本章就是讲了一些measurement of algorithms.
比如three-sum problem，
因为这个问题就是相当于从一个数组中选3个的个数，所以是 ，然后因为有三个数组，所以数组访问次数要乘以3，因此就是 。
常用的order-of-growth：
还介绍了下数学分析，以BinarySearch为例：
证明了Binary Search 只用至多 次比较。证明比较有意思，可以看下：
课程中还举了个例子，怎么使用Binary Search 把 Three-Sum问题的Order of Growth达到
我写了下代码实现：
Big Theta (Θ), Big Oh (O), Big Omega (Ω)
- Big Theta (Θ) - 表示准确的渐近增长率
- Big Oh (O) - 表示上界
- Big Omega (Ω) - 表示下界
最后一讲则是讨论memory，java中常用的数据类型的memory占用如下：
数组中额外有24bytes是数组对象的头部开销，包括
- 对象头 (16 bytes)
- 数组长度字段 (4 bytes)
- 内存对齐填充 (4 bytes, 使其对齐到 8 字节的倍数)
下面这张图则展示了String对象的内存分配。
在 Java 64 位 JVM（默认启用
Compressed Oops）的情况下，String 对象的内存分配如下：组件 | 占用 (字节) | 说明 |
对象头 (Object Overhead) | 16 | 8B Mark Word + 8B Class Pointer |
value (char[] 引用) | 8 | 存储 char[] 数组的引用（指向堆中的字符数组） |
offset | 4 | int 类型，占 4 字节 |
count | 4 | int 类型，占 4 字节 |
hash | 4 | int 类型，占 4 字节 |
填充 (Padding) | 4 | JVM 需要 8 字节对齐，填充 4 字节 |
合计 (不含字符数组) | 40 | 16（对象头）+ 8（引用）+ 12（int 变量）+ 4（填充） = 40 字节 |
char[] 数组存储在堆 (Heap) 内存中：
- 对象头 (16B) + 长度字段 (4B) + 填充 (4B) + N × 2B (字符存储)
- 总占用：2N + 24 字节
所以String 对象一共占用 2N+60 字节，但是因为还有 4 字节的 padding。所以一共是 2N + 64 字节。java除了8种基本数据类型之外，其他对象类型（包括数组）都是引用类型。
以Weighted Quick Union 举例，内存占用如下：
Interview Questions
[!NOTE] Q1 3-SUM in quadratic time Design an algorithm for the 3-SUM problem that takes time proportional to in the worst case. You may assume that you can sort the integers in time proportional to or better.
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
这道题的思路是使用双指针，先开始一个循环，然后从i+1到n之间用双指针找两个数，使得和前一个数的和为0。这里可能的错误点在于什么时候跳过来避免重复。
代码示例：
[!NOTE] Q2 Search in a bitonic array In array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of distinct integer values, determines whether a given integer is in the array.
- Standard version: Use compares in the worst case.
- Signing bonus: Use compares in the worst case (and prove that no algorithm can guarantee to perform fewer than compares in the worst case).
Bitonic数组是指先递增然后递减的数组。总体思路是首先找出“峰值”元素，然后在递增和递减的部分分别用二分法搜索给定的目标值。
代码示例：
代码中需要注意的是找峰值peak的时候，没法用(nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])来判断找到了，因为会产生越界问题。可以设定low < high,然后让high每次更新的指向mid，这样可以确保最后的峰值是low。
[!NOTE] Q3 Egg drop Suppose that you have an -story building (with floors 1 through ) and plenty of eggs. An egg breaks if it is dropped from floor or higher and does not break otherwise. Your goal is to devise a strategy to determine the value of given the following limitations on the number of eggs and tosses:
- Version 0: 1 egg, tosses.
- Version 1: eggs and tosses.
- Version 2: eggs and tosses.
- Version 3: 2 eggs and tosses.
- Version 4: 2 eggs and tosses for some fixed constant .
这里version0 就是简单的遍历一遍，version1就是二分查找。
version2要求logT的次数，可以先指数搜索，1，2，4，8这样搜索，达到logT次的投掷次数。然后第二次再线性搜索，这里的复杂度也不超过logT，因为比如在第16层停止，要从8到16线性搜索，肯定小于log8<=logT。
version3则根据题意，设置步长为,因为只有两个蛋，第二次只能线性搜索。第一次的复杂度~
，假设n = 100，每次步长为10，第一次肯定不超过10次。第二次从步长里线性搜索，也不超过10次。
version4则要求的复杂度，这里可以参考version2，因为只有两个蛋，第二次只能线性，可以使用三角数增量，第第 次试验在 楼层，那么k基本是就是。线性回溯也是一样的，从,复杂度为,所以题目的常数C等于。
对照表：version2, version3, version4
版本 | 思路 | 最坏投掷次数 | 简要复杂度证明 |
version2 ( eggs, tosses) | 指数搜索 + 二分搜索 1. 从 1、2、4、8… 成倍向上探测，直到发现首次破碎； 2. 在上一次安全楼层和此次破碎楼层之间二分查找。 | 1. 指数搜索需要 次投掷缩小范围；2. 二分查找再 次；合计 。 | |
version3 (2 eggs, tosses) | 固定步长 = 1. 先按固定的区间大小 往上跳(1, , …)； 2. 鸡蛋破碎后，在该区间内用线性搜索。 | 1. 跳跃阶段最多 次;2. 再线性搜索最多 次;合并得到 。 | |
version4 (2 eggs, tosses)* | 三角数增量 (1,3,6,10…) 1. 第 次试验在 楼层； 2. 破碎后在线性搜索上一段区间。 | 若在第 次破碎，则，解得 ；线性回溯也需 ，总 =。 |
代码展示：
这一讲最经典的问题就是抛鸡蛋问题，需要经常回顾。
- 作者:很久不是自己
- 链接:https://weibo.com/article/algorithms-part1-module3
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。