版本 Windows 11 企业版
版本号 24H2
安装日期 2024/11/27
操作系统版本 26100.3476
体验 Windows 功能体验包 1000.26100.54.0
云端存储服务提供商： S3
外观配置：
系统日志：systemlog.zip
v3.1.24 状态异常，重建索引后部分内容缺失
相关帖子
-
-
-
-
没有，偶发的丢失；当就目前这个文档出现了这个问题，我猜测可能是数学公式的原因，下面是当前编辑文档的内容：
1. 算法
- 算法(algorithm)：对特定问题求解步骤的一种描述，是指令的有限序列，其中一条指令表示一个或多个操作
- 5 个重要特性
- 有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步后结束，且每一步都可在有穷时间内完成
- 确定性：
- 算法中每条指令必须有确切的含义，不会产生二义性。
- 在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出
- 可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的
- 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合
- 输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量
- 5 个重要特性
2. 算法设计的要求
- 正确性(correctness)：算法应当满足具体问题的需求。
- 需求：至少应当包含对输入、输出和加工处理等的明确的无歧义性的描述
- 正确性的 4 个层次：（通常以第 3 层意义的正确性作为衡量一个程序是否合格的标准）
- 程序不含语法错误
- 程序对于几组输入数据能够得出满足规格说明要求的结果
- 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果
- 程序对于一切合法的输入数据都能产生满足规格说明要求的结果
- 可读性(readability)：算法主要是为了人的阅读与交流，其次才是机器执行。
- 健壮性(robustness)：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果
- 处理出错的方法：返回一个表示错误或错误性质的值，并终止程序的执行 -> 以便在更高的抽象层次上进行处理
- 效率与低存储量需求：
- 效率：算法执行的时间，执行时间短的算法效率高
- 存储量需求：算法执行过程中所需要的最大存储空间
3. 算法效率的度量
-
两种度量程序执行时间的方法：
-
计算算法关于 n 的增长率或阶 的 示例
for (i=2; i<=n; ++i) for (j=2; j<=i-1; ++j) {++x; a[i][j]=x;}- ++x 的语句频度计算
-
统计 ++x; 的执行次数：
T(n) = \sum_{i=2}^{n} \sum_{j=2}^{i-1} 1
其中：- 外层循环：i 从 2 取到 n，共 次。
- 内层循环：j 从 2 取到 i-1，共 次。
-
内层求和
T(n) = \sum_{i=2}^{n} \sum_{j=2}^{i-1} 1
内层求和 表示，在固定的 i 之下，j 从 2 到 i-1 之间的所有整数，每次 j 运行时 ++x; 都会执行 1 次，因此它的求和结果就是 j 的取值范围的长度：
\sum_{j=2}^{i-1} 1 = (i-2)
-> 求和问题变成：
T(n) = \sum_{i=2}^{n} (i-2) -
拆分求和
T(n) = \sum_{i=2}^{n} i - \sum_{i=2}^{n} 2- 计算第一项：1 到 n 的和 --> i 是从 2 开始的，所以我们需要 去掉 i=1 的项
\sum_{i=1}^{n} i = \frac{n(n+1)}{2}
\sum_{i=2}^{n} i = \frac{n(n+1)}{2} - 1- 计算第二项：i=2 到 n 之间，每一项都是 2，共有 ( n-1 ) 项
\sum_{i=2}^{n} 2 = 2(n-1)
-
代入计算
T(n) = \left(\frac{n(n+1)}{2} - 1\right) - 2(n-1)
展开：
T(n) = \frac{n(n+1)}{2} - 1 - 2n + 2
T(n) = \frac{n^2 + n}{2} - 2n + 1
T(n) = \frac{n^2 + n - 4n + 2}{2}
T(n) = \frac{n^2 - 3n + 2}{2} -
最高阶项的增长趋势
- 最高阶项是，所以 T(n) 的增长率是：
-
- ++x 的语句频度计算
4. 算法的存储空间需求
1 回复 - 算法(algorithm)：对特定问题求解步骤的一种描述，是指令的有限序列，其中一条指令表示一个或多个操作
-
-
-
-
-
-
请输入回帖内容
...
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于