缪之灵

算法分析基础 算法分析基本概念 算法分析（analysis of algorithms） 是对一个算法需要多少计算时间和存储空间作定量得分析，确定算法在什么样得环境下能够有效地运行。分析其在最好、最坏和平均情况下的执行情况，并对同一问题不同算法的有效性作出比较。 全面分析算法的两个阶段： 事前分析（a priori analysis）： 确定每条语句的执行次数； 求出该算法的一个时间限界函数（关于问题规模 n 的函数）。 事后测试（a posterior testing）： 作时空性能分布图。 算法的执行时间： 同一条语句在一个算法中的执行次数称为频率计数（frequency count），由算法直接确定，与所用的机器无关，且独立于程序设计语言。 语句的时间总量 = 频率计数 × 执行一次该语句所需要的时间 算法的执行时间就是构成算法的所有语句的执行时间总量之和。 时间复杂度的形式化定义： 算法的时间复杂度用 T(n)T(n)T(n) 表示，空间复杂度用 S(n)S(n)S(n) 表示，其中 nnn 是问题的规模。 最坏情况下： Tmax(n)=max⁡{T(I ...

随机试验与随机事件 随机试验 在自然界和人类社会中出现的各种现象大致可以分为两类：必然现象和随机现象。在一定条件下必然出现的现象叫做必然现象；在相同的条件下，可能出现不同的结果，而在试验或观测之前不能预知确切的结果的现象叫做随机现象。 为了研究和揭示随机现象的统计规律性，我们需要对随机现象进行大量重复的观察、测量或试验。具有以下特点的试验称为随机试验： 可重复性：可以在相同条件下重复进行； 可观测性：每次试验的所有可能结果都是明确的，可以观测的，并且试验结果有两个或两个以上； 随机性：每次试验结果不确定。 随机试验简称试验，通常用字母 EEE 表示。随机试验 EEE 的基本结果称为样本点，用 ω\omegaω 表示。称随机试验 EEE 的所有基本结果的集合为样本空间，用 Ω=∣ω∣\varOmega = |\omega|Ω=∣ω∣ 表示。 随机事件及其运算 我们把随机试验 EEE 的样本空间 Ω=∣ω∣\varOmega = |\omega|Ω=∣ω∣ 的子集称为随机试验 EEE 的随机事件，简称为事件，用大写字母 A,B,CA, B, CA,B,C 等表示。设 A⊆ΩA \sub ...

计算机系统概述 计算机系统的层次结构 下列层次结构由低到高： 硬件部分： 微程序机器 M0（微指令系统）：由硬件直接执行微指令。 传统机器 M1（机器语言机器）：二进制机器语言直接在 M1 上执行。 软件部分： 虚拟机器 M2（操作系统机器）：用机器语言解释操作系统。 虚拟机器 M3（汇编语言机器）：将汇编语言程序先由汇编程序翻译成机器语言程序，再在 M1 上执行。 虚拟机器 M4（高级语言机器）：将高级语言程序先由编译程序翻译成汇编语言程序，再在 M2、M1（或直接到 M1）上执行。 冯·诺依曼结构的基本思想 最重要思想：存储程序 工作方式： 把要完成的工作编写为程序，将程序和数据送入主存并执行。程序一旦启动，计算机能够自动完成逐条取出指令和执行指令的任务。（控制流驱动） 特点： 采用 “存储程序” 的工作方式； 由五大部件组成（运算器、存储器、控制器、输入设备、输出设备）； 指令和数据用二进制代码表示； 指令和数据以同等地位存储在存储器中，形式上两者没有区别，但计算机应能区分； 指令由操作码和地址码组成，可按地址访问并顺序执行指令； 以运算器为中心（现在一般以 ...

终端和文件初级操作 登录 Linux 终端 1. 输入账号密码登录 2. 使用 shell help命令：查看命令的帮助列表。 1help [option] <command> man命令：进入命令的帮助手册页面，比help显示的信息更详细。 1man [option] <command> 查看系统的使用者信息（登录名，终端号和登录时间）和当前登录的用户信息： 12whowho am i date命令：显示当前的系统日期和时间。 cal命令：显示指定年月的日历表。 1cal <month> <year> tty命令：显示当前连接到标准输入的终端的文件名。 file命令：用于辨识文件类型。 1file [option] <filename> 3. 退出当前用户 执行[Ctrl-D]、exit或logout命令退出当前终端。 vi 初级操作 1. 打开 vi 1vi <filename> 2. 文件录入和修改 切换至命令模式：esc 键。 使用 “u” 命令撤销上一步操作，使用 “r” 命令重做上一步操作。 切换至 ...

在本文中，我们将了解级数和常微分方程的基础概念，大致掌握它们的求解方式。

数据结构的定义 数据的逻辑结构 数据由多个数据元素（data element） 组成，而数据的逻辑结构（logical structure） 讨论的是数据元素之间的逻辑关系，一般可以用 “节点” 、“前驱” 、“后继” 等概念进行刻画。 一个逻辑结构可以在形式上被定义为二元组 B=(D,R)B = (D, R)B=(D,R)，其中 DDD 表示数据元素的集合，RRR 表示 DDD 上的二元关系 rrr 的集合。 设 a,b∈Da, b \in Da,b∈D，且关系 ⟨a,b⟩∈r\langle a, b \rangle \in r⟨a,b⟩∈r，则称 aaa 为 bbb 的前驱节点，称 bbb 为 aaa 的后继节点；如果不存在 a∈Da \in Da∈D，使得 ⟨a,b⟩∈r\langle a, b \rangle \in r⟨a,b⟩∈r，则称 bbb 为开始节点；如果不存在 b∈Db \in Db∈D，使得 ⟨a,b⟩∈r\langle a, b \rangle \in r⟨a,b⟩∈r，则称 aaa 为终端节点；既非开始节点又非终端节点的节点被称为内部节点。 逻辑结构的分类： ...

在阅读完 Effective C++ 后，笔者继续阅读了原作者针对 C++11/14 而写的 Effective Modern C++，并结合自己的理解对原书内容进行总结归纳，写下阅读笔记以便日后参考。 如果你对 Effective C++ 的内容感兴趣，可以参阅：一篇文章学完 Effective C++：条款 & 实践 第一章：类型推导 条款 1：理解模板类型推导 函数模板大致形如： 12template<typename T>void f(ParamType param); 在编译期，编译器会通过表达式推导出两个类型：一个是T的类型，另一个是ParamType的类型，这两个类型往往不一样，ParamType常包含一些饰词，如const或引用符号等限定词。 情况 1：ParamType 是个指针或引用，但不是个万能引用 若表达式具有引用类型，则先将引用部分忽略。 对表达式的类型和ParamType进行匹配来决定T的类型。 12345678910template<typename T>void f(T& param);int x = 27;c ...

机械振动 简谐振动的方程 物体在一定位置附近的位移变化满足余弦（或正弦）规律，称为简谐振动（simple harmonic motion）。 对于弹簧振子而言，在弹性限度内，弹性力可由胡克定律（Hooke’s law） 计算： F=−kxF=-kx F=−kx 角频率 ω\omegaω： （单位为 rad⋅s−1rad\cdot s^{-1}rad⋅s−1） ω2=km(或 ω=km)\omega^2=\frac k m\quad\left(\text{或}\ \omega=\sqrt{\frac k m}\right) ω2=mk​(或 ω=mk​​) 加速度 aaa： a=Fm=−(km)x=d2xdt2=−ω2xa=\frac F m=-\left(\frac k m\right)x=\frac{\mathrm{d}^2x}{\mathrm{d}t^2}=-\omega^2x a=mF​=−(mk​)x=dt2d2x​=−ω2x 周期 TTT： ωT=2πT=2πω=2πmk\omega T=2\pi\\ T=\frac{2\pi}{\omega}=2\pi\sqrt{\frac ...

在本文中，我们紧接着之前对多元函数的认识，了解多元函数积分以及曲线曲面积分的相关内容。

摄像机 在光线生成着色器中，我们需要根据摄像机所处的坐标和朝向来发出射线。在光栅化中，我们会计算出观察矩阵和投影矩阵，这两个矩阵也可以用于推算出射线信息，就不再需要存储额外的相机信息。 首先计算出屏幕的像素坐标相关信息： 123456// raygen.hlsl// Calculate pixel informationfloat2 pixelCenter = DispatchRaysIndex().xy + (float2) 0.5f;float2 screenPos = pixelCenter / DispatchRaysDimensions().xy;screenPos = screenPos * 2.0f - 1.0f; 根据求得的像素坐标，应用观察矩阵和投影矩阵的逆即可获得射线的原点和方向，这个过程实际上是在将视锥体逆推回世界空间中： 1234567891011121314151617181920212223242526272829303132333435363738// raygen.hlsl#include "raycommon.hlsl"struct ...