量化交易：最大回撤（Drawdown）算法

写在前面：

本文为本人学习用于回测报告中的最大回撤算法指标时整理的学习笔记，欢迎沟通交流~

一、基本概念

1.1 最大回撤（Max Drawdown）

回撤：对于任意日期区间，回撤 = 钱包的亏损比例 =（现值 - 原值）/ 原值 = 现值 / 原值 - 1 = 缩水比例 - 1，若结束值相对起始值未下降，则回撤为0.0。

最大回撤：相当于一位最不幸的投资者，在一个最糟糕的日期买入，随后在另一个最糟糕的日期卖出，亏损比例（绝对值）比任何两个其他日期的买卖都高。所有日期区间中回撤绝对值最大的，当有多个最大回撤相等时，只选一个（<= 0.0），选择规则是：

• 等值最大回撤对应的日期区间重叠时：选日期区间最狭窄的；
• 等值最大回撤对应的日期区间不重叠时：选日期区间最晚的。
  • 出现该情况时，晚的区间的峰值和谷值一定高于或等于早的区间的峰值和谷值。

最大回撤区间：最大回撤对应的起始日期和结束日期。

最大回撤意义：通常用于衡量和比较股票、基金、指数的波动下行风险。在经过长期波动后，最大回撤较小的股票，通常有更大的长期涨幅，也对挑选合适的入场时机有一定的参考价值。

对数图：金融产品的走势图，应该都使用对数图，或者与对数图等价的等比例图。在对数图上，两个值的对数之间的垂直距离与缩水比例线性相关，而缩水比例与回撤正相关，即log(low / high) = log(low) - log(high)。

等比例：任何3条相邻距离相等的水平线，上2条水平线的数值比例，与下两条水平线的数值比例相等，也就是他们的对数的差相等。

等比例图：与对数图的水平线一致，但标识的数值不是对数而是原数值。

示例：如何使用对数图及其重要性

1.2 斐波那契回撤（Fibonacci Drawdown）

斐波那契回撤线（Fibonacci Retracement）是指能够发现资产价格潜在支撑位与压力位的水平线。斐波那契回撤水平线允许交易者在任意两个价格点之间绘制（通常是高点与低点）。 23.6%、38.2%、50%、61.8%和78.6%是斐波那契水平的百分比，表示资产价格可能出现停滞或逆转的区域。

斐波那契回撤意义：在技术分析中，当股价或其他资产价格在上涨趋势中出现回调时，交易者通常会将斐波那契回撤水平作为潜在的支撑位来观察。如果价格在靠近这些水平时显示出反弹迹象，这可能是一个入场的时机。

例如，假设某股票价格从10美元上涨到20美元，然后开始回调。斐波那契回撤工具可以帮助确定可能的支撑位，如23.6%的回撤水平大约在18.26美元，而50%的回撤水平在15美元。交易者可以观察这些水平是否与其他技术指标或趋势线相互确认，来确认是否进行买入操作。

二、最大回撤算法设计

2.1 输入

一个结构或类型（struct or class）的列表或数组（array or list），至少包含两个域或者属性（field or attribute）：域具体内容日期按升序排列并且没有重复数值通常代表指数、后复权价、累计净值等，均为正实数（正浮点数）

2.2 处理

根据输入计算出列表或数组中的最大回撤及区间的起止点。

2.3 输出

最大回撤（<= 0.0），最大回撤区间起始日期及数值，最大回撤区间结束日期及其数值。

2.4 算法分析

按照定义回撤只能是0.0或者负数，所谓回撤最大，指的是回撤的绝对值最大。只要列表或者数组非空，从任一点出发，到它**以后***的点，都一定有一个最大回撤。

以后*：包含自身，“之后”则不包含自身。

• 如果某个点是最后一个点，则它只有一个以后的点，即自身，那么从此点开始的最大回撤就是0.0；
• 如果某个点的值比它之后所有点的值都低或者相等，那么从此点到其以后任意点的回撤全部；
• 每个点到它之后的任一点，都可以计算出回撤，这些回撤中必有一个最大的（多个最大回撤相同时按规则选取）；
• 所有起始点的最大回撤中，再选出最大的，就是整个列表或数组的最大回撤。
• 以上即为遍历算法的基本思想。

2.4.1 遍历算法

算法思想：通过遍历数组中的每个点，将其视为可能的峰值，然后从这一点遍历到数组末尾，寻找与该峰值相比的最小回撤。

算法流程：

1. 初始化：1. 设定整体最大回撤为1.0 (一个不可能的值)2. 初始化整体最大回撤的起点和终点位置为空
2. 对于列表或数组中的每个点 i:a. 初始化本轮最大回撤为1.0 (一个不可能的值)b. 初始化本轮最大回撤的终点位置为空
3. 对于每个点 i，计算它到它以后所有点 j 的回撤值：a. 计算从点 i 到点 j 的回撤值b. 若回撤值 < 本轮最大回撤：- 更新本轮最大回撤为当前回撤值- 记录起点 i 和终点 j 作为本轮最大回撤的起点和终点c. 若回撤值 == 本轮最大回撤且起点 i 相同：- 比较终点位置，若当前终点 j 更早，则更新终点为 j
4. 比较本轮最大回撤和整体最大回撤：a. 若本轮最大回撤 <= 整体最大回撤：- 更新整体最大回撤为本轮最大回撤- 更新整体最大回撤的起点和终点位置
5. 重复步骤 2-4，直到所有点 i 都已作为起点计算过回撤
6. 输出整体最大回撤及其对应的起点和终点位置

关键理解点：

若本轮最大回撤<=整体最大回撤，则将整体最大回撤替换为本轮最大回撤。之所以相等时也替换，是因为【1】若区间重叠，晚的起点区间更狭窄；【2】若区间不重叠，也要选晚的。

遍历算法的优化：

1. 初始化：1. 设定整体最大回撤为1.0 (一个不可能的值)2. 初始化整体最大回撤的起点和终点位置为空
2. 对于列表或数组中的每个点 i 作为起点:a. 初始化本轮最低点为 i 处的值b. 初始化本轮最大回撤为1.0 (一个不可能的值)c. 初始化本轮最大回撤的终点位置为空
3. 对于每个点 i，遍历从 i+1 到列表或数组末尾的每个点 j：a. 如果 j 处的值小于本轮最低点：- 更新本轮最低点为 j 处的值- 计算从点 i 到点 j 的回撤值- 更新本轮最大回撤为该回撤值- 记录终点 j 作为本轮最大回撤的终点位置b. 如果 j 处的值等于本轮最低点且 j 更早出现（即 j 更靠前）：- 仅更新终点为 j- 计算新的回撤值并与本轮最大回撤比较，若有必要则更新本轮最大回撤
4. 比较本轮最大回撤和整体最大回撤：a. 若本轮最大回撤 <= 整体最大回撤：- 更新整体最大回撤为本轮最大回撤- 更新整体最大回撤的起点和终点位置
5. 重复步骤 2-4，直到所有点 i 都已作为起点进行过处理
6. 输出整体最大回撤及其对应的起点和终点位置

关键优化点：

仅计算最低点的回撤：对于每个起点，找到它之后的最低点（若有多个最低点，选择最早的），然后计算该最低点的回撤即可。

时间复杂度：$$O(n^2)$$

空间复杂度：$$O(1)$$

2.4.2 简洁算法

算法思想：采用二分查找的方法，逐步缩小搜索范围，以找到最大回撤。

算法流程：

按最低点分解：

1. 初始化：1. 设定整体最大回撤为1.0 (一个不可能的值)2. 初始化整体最大回撤的起点和终点位置为空
2. 从整个列表或数组中找到最低点：1. 若有多个相等的最低点，选择最早出现的最低点2. 记录此最低点的位置
3. 划分列表或数组为两部分：1. **前半段**（最低点以前）2. **后半段**（最低点之后）
4. 对前半段进行处理：a. 找到前半段的最高点（若有多个，选择最晚的一个）b. 计算前半段最高点到最低点的回撤值c. 记录前半段的最大回撤
5. 对后半段进行递归处理：a. 如果后半段为空，则跳过b. 找到后半段的最低点，若有多个相等的最低点，选择最早出现的c. 划分后半段为新的前半段和新的后半段d. 计算新的前半段的最大回撤e. 递归处理新的后半段，重复步骤 4 和 5
6. 比较前半段和后半段的最大回撤：1. 更新整体最大回撤为前半段和后半段中的最大值2. 若回撤值相同，则选择最晚出现的回撤
7. 输出整体最大回撤及其对应的起点和终点位置

关键步骤说明：

• 找到最低点：确定整个列表或数组的全局最低点，分割为前半段和后半段。
• 前半段处理：计算前半段内的最大回撤值，并将其作为前半段的回撤结果。
• 后半段递归处理：对后半段应用相同的算法，递归拆分和计算，直到整个数组都处理完。
• 比较和更新：将前半段和后半段的最大回撤进行比较，更新整体最大回撤值。

时间复杂度：