UpdateTime 2021-12-04

关于算法的描述 所谓一个问题是指一个有待回答、通常含有几个取值还未确定的自由变量的一个一般性提问。 它由两部分构成: 一是对其关于参数的一般性描述; 二是对该问题的答案所应满足的某些特性的说明。 而一个问题的某个实例则可通过指定问题中所有参数的具体取值来得到。以下用 ΠΠ 表示某个问题,用 ΙΙ 表示其实例。 所谓一个问题实例的大小是指 为描述或表示它而需要的信息量。 所谓算法是指用来求解某一问题的、带有一般性的一步一步的过程。它是用来描述可在许多计算机上实现任一计算流程的抽象形式,其一般性可以超越任何

UpdateTime 2021-10-28

这里说的都是我的一派胡言,不足为信! 如果相对简单的方法可以工作,那么请坚持这种方法! 基础概念 我们希望通过某种方式,来获得一个函数,这个函数可以从数据中自动获得函数的对应关系; 比如:假设我们想要做一个识别图片是猫🐱还是狗🐕的程序,此时图片就是输入,而是不是猫,或者是不是狗就是输出;而图片可以是一些列像素点的集合,可以以某种二进制的形式来表示,于是这一长串二进制数就是定义域,而值域只有两个值 0 和 1,意味着是不是猫,因为不是猫那就是狗; 再比如:假设要识别单独的手写数字,那么值域就变成了 0

UpdateTime 2021-10-11

分数背包问题 贪心选择性质的证明 设 II 为背包问题,其中设: nn 为其中物品的数量 v_iv_i 为第 ii 个物品的价值 w_iw_i 为第 ii 个物品的重量 物品以 v_i/w_iv_i/w_i 递增排序 W > w_nW > w_n 为背包的容量 设 S = (s_1, s_2, \cdots, s_n)S = (s_1, s_2, \cdots, s_n) 为一个解,贪心算法假设 s_n = \min(w_n, W)s_n = \min(w_n, W),然后继续求解子问题 I' = (

UpdateTime 2021-10-03

一点历史 1977年,三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字的首字母命名,叫做 RSA 算法。从那时直到现在,RSA 算法一直是最广为使用的 非对称加密算法。毫不夸张地说,只要有计算机网络的地方,就有 RSA 算法。 互质关系 如果两个正整数,除了 11 以外,没有其他公因子,我们就称这两个数是 互质 关系,或者 互素 关系。 关于互质关系,不难得到以下结论: 任意两个质数构成互质关系,比如 1313 和 6161

UpdateTime 2021-10-03

Introduction 介绍 The recent development of various methods of modulation such as PCM and PPM which exchange bandwidth for signal-to-noise ratio has intensified the interest in a general theory of communication. 最近,对于调制的多种方法的开发,例如 PCM 和 PPM,在通信的一般理论中,他们增强了对

UpdateTime 2021-10-03

有关 欧几里得算法,参考 辗转相除法 定理 如果 a, b \in \mathbb{N^+}a, b \in \mathbb{N^+},那么 (a, b) = s_na + t_n b(a, b) = s_na + t_n b 其中,s_n, t_ns_n, t_n 是下面定义的递归序列的第 nn 项 \begin{aligned} s_0 = 1, t_0 = 0, \\ s_1 = 0, t_1 = 1, \\ \end{aligned} \begin{aligned} s_0 = 1, t_0

UpdateTime 2021-09-21

DSA 的主要参数 全局公开密钥分量 pp:素数,要求 2^{L-1}<p<2^L2^{L-1}<p<2^L,且 LL 为 6464 的倍数 取 p = 127p = 127 qq:(p - 1)(p - 1) 的素因子,2^{159} < q < 2^{160}2^{159} < q < 2^{160},即比特长度为 160160 位 则 p - 1 = 126 = 2 \times 3^2 \times 7p - 1 = 126 = 2 \times 3^2 \times 7,故取 q =

UpdateTime 2020-12-17

重置 开始 暂停 停止 减速 加速 概述 排序的过程,实际上是减少逆序数的过程。 排序算法稳定性:假设待排序的序列中,存在相同的关键字,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。 冒泡排序 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换

UpdateTime 2020-12-10

概述 时钟周期(Clock Cycle):通常为节拍脉冲或T周期,即主频的倒数,是CPU中最小的时间单位。 主频:机器内部的时钟频率。时钟周期的倒数。 CPI (Clock cycle Per Instruction):执行一条指令所需的时钟周期数。 CPU执行时间:运行一个程序所花费的时间 \displaystyle CPU执行时间 = \frac{CPU时钟周期数}{主频} = \frac{指令条数 \times CPI}{主频}\displaystyle CPU执行时间 = \frac{CPU时钟周

UpdateTime 2020-11-28

绪论 时间复杂度 T(n)T(n) 时指算法中所有语句的频度(执行次数)之和。 渐进时间复杂度是当 nn 趋于无穷时 T(n)T(n) 的数量级,而非 T(n)T(n) 的准确大小,因此以 T(n) 的数量级来表征时间复杂度。 加法规则: T(n) = T_1(n) + T_2(n) = O[f(n)] + O[g(n)] = O[\max\left\{f(n), g(n)\right\}] T(n) = T_1(n) + T_2(n) = O[f(n)] + O[g(n)] = O[\max\le