For an algorithm, it is generally necessary to calculate its time complexity and space complexity to measure its efficiency. However,
Category: Courses
SAT and 3-SAT
【SAT Questions】 Call the Boolean satisfiability problem SAT: Given a set of clauses C_1,C_2,…,C_n on the set of variables X={{x_1,x_2,…,x_n}},
什么是算法(Algorithm)?算法的性质是什么?算法与程序的区别?
1 什么是算法? 算法是指解决问题的一种方法或一个过程。 2 算法的性质 算法是若干指令的有穷序列,满足性质: (1)输入:有外部提供的量作为算法的输入。 (2)输出:算法产生至少一个量作为输出。 (3)确定性:组成算法的每条指令是清晰,无歧义的。 (4)有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。 3 什么是程序? 程序是算法用某种程序设计语言的具体实现。 4 程序与算法的区别 程序可以不满足算法的性质(4)。 例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。 操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止 0
Orders of Growth(计算复杂度排行)
常见的时间复杂度从小到大的顺序依次是: Θ(lgn),Θ(sqrt(n)),Θ(n),Θ(nlgn),Θ(n^2 ),Θ(n^3 ),Θ(2^n ),Θ(n!)。 0
Asymptotic Notation
1 How to measure the running speed of an algorithm? How to measure the running speed of an algorithm? What
Asymptotic Notation(渐进表示法、渐进分析)
1 How to measure the running speed of an algorithm?(如何衡量一个算法的运行速度?) How to measure the running speed of an algorithm? What
计算机是如何存储数据的?寄存器+内存
参考视频:https://www.youtube.com/watch?v=fpnE6UAfbtU&feature=youtu.be 图片是从视频中截取的,版权问题归 CrashCourse 作者。这里仅仅做学习使用。 (The images were captured from the video. The copyright is reserved for the CrashCourse authors. Here
CPU如何执行一个程序(一条指令)?取指—译码—执行—写回过程
简介 对于一个CPU来说,执行指令一般要经过四个流程: 1.取指 2.译码 3.执行 4.写回 1 取指 在此图中,有程序计数器(PC)、存储器地址寄存器(MAR)、存储器数据寄存器(MDR)、控制器(CU)、内存(Memory)五个组件。内存当前的指令为(ADD:R1,R2),内存地址为101。 程序计数器指向当前指令在主存的位置。即PC指向内存的101地址。PC所指向的内容会放到指令地址总线上,对指令启动读命令。在一条指令取出后,PC指针指向的地址会加1,即指向102地址。 控制器将PC中的指令地址通过内部总线传输到MAR中。 MAR存储了指令或数据的内存地址。MAR将控制指令传输到地址总线上。 控制单元通过MAR提供的地址,发送信号访问存储器并进行读操作。 存储器通过地址译码器查到存储地址为101的存储单元的内容(ADD:R1,R2),并将存储单元的内容传送到MDR中。 MDR中保存的数据通过内部总线传送给IR寄存器(指令寄存器)。 至此,取指令部分完成! 2 译码 MDR中保存的数据通过内部总线传送给IR寄存器。指令包含操作数和地址码两部分。 IR寄存器会分析出操作码部分和地址码部分。将操作码送入解码器,解析出ADD是加操作。
证明NPC问题的通用策略
证明NPC问题的通用策略 给定一个基本的问题X,证明其是NPC的基本策略是: (1)证明X是一个NP问题。 (2)选择一个已知的NPC问题Y。 (3)证明Y \leq_p X。 0
子集和问题是NP完全的
【子集和问题】 给定自然数w_1,w_2,…,w_n和目标值W,问{w_1,w_2,…,w_n}有一个子集加起来恰好等于W吗? Ex: { 1, 4, 16, 64, 256, 1040, 1041, 1093, 1284, 1344 }, W = 3754. Yes. 1
三维匹配问题是NP完全的
【三维匹配问题】 给定三个不相交的集合X、Y、Z,三个集合的大小都为n。给定一个三元组集合T \subseteq X \times Y \times Z,集合T的大小为m。 问:T中是否存在一个大小为n的子集T’,这个子集恰好包含X,Y,Z每个元素一次。 三维匹配问题其实是集合覆盖和集合包装问题的特例。 三维匹配问题是NP完全的 首先,很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n,且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的,可以通过3-SAT\leq_p三维匹配证明。 【3-SAT\leq_p三维匹配证明】 考虑任意的一个3-SAT实例,有n个变量x_1,x_2,…,x_n和k个子句C_1,C_2,…,C_n。构造3DM实例X,Y,Z,T。 对于每一个变量,都有一个零件相对应。如图9所示。每个零件有Core(核心)元素、Tip(边梢)元素、Triple元组。每一个零件大大小为2k。k为子句的大小。\ 则,对于每一个变量x_i,建立: A_i={a_{i,1},a_{i,2},…,a_{i,2k}}。 B_i={b_{i,1},b_{i,2},…,b_{i,2k}}。 t_{i,j}={(a_{i,j},a_{i,j+1},b_{i,j}}。 构造的零件如图9所示。