asp.net搭建网站,搭建棋牌工具,wordpress用户中心商城,wordpress1.4算法概述
所谓算法#xff0c;即特定计算模型下#xff0c;旨在解决特定问题的指令序列 输入 待处理的信息#xff08;问题#xff09; 输出 经处理的信息#xff08;答案#xff09; 正确性 的确可以解决指定的问题 确定性 任一算法都可以描述为一个由基本操作组成的序…算法概述
所谓算法即特定计算模型下旨在解决特定问题的指令序列 输入 待处理的信息问题 输出 经处理的信息答案 正确性 的确可以解决指定的问题 确定性 任一算法都可以描述为一个由基本操作组成的序列 可行性 每一基本操作都可实现且在常数时间内完成 有穷性 对于任何输入经有穷次基本操作都可以得到输出 … 程序未必是算法例如发生死循环或者栈溢出时。
算法在满足基本要求时最重要的是速度尽可能快存储空间尽可能少效率。
计算模型
两个主要方面 1.正确性算法功能与问题要求一致 2.成本运行时间 存储空间
计算成本 T ( n ) max { T ( P ) ∣ ∣ P ∣ n } T(n)\max \{T(P) \space \boldsymbol | \space |P| n \} T(n)max{T(P) ∣ ∣P∣n} 遵守最坏情况分析原则。
特定问题不同算法下需要抽象出一种理想的平台或模型不再依赖于种种具体因素从而直接准确地描述、测量并评价算法。
渐进复杂度
随着问题规模地增长运算成本增大 T ( n ) O ( f ( n ) ) if ∃ c 0 , n ≫ 2 , T ( n ) c ⋅ f ( n ) T(n) \mathcal O(f(n)) \space \text{if } \exists \space c0,n\gg 2, T(n)c\cdot f(n) T(n)O(f(n)) if ∃ c0,n≫2,T(n)c⋅f(n)
与 T ( n ) T(n) T(n) 相比 f ( n ) f(n) f(n)更为简洁但依然反应前者地增长趋势
常系数可忽略 O ( f ( n ) ) ( c × f ( n ) ) \mathcal O(f(n)) (c \times f(n)) O(f(n))(c×f(n)) 低次项可忽略 O ( n a n b ) O ( n a ) a b 0 \mathcal O(n^an^b)\mathcal O(n^a)ab0 O(nanb)O(na)ab0 1.常数复杂度为 O ( 1 ) \mathcal O(1) O(1) 算法不含转向循环、调用、递归等必顺序执行即复杂度为 O ( 1 ) \mathcal O(1) O(1)
2.对数复杂度为 O ( log n ) \mathcal O(\log n) O(logn) ∀ c 0 , l o g ( n ) O ( n c ) \forall c0,log(n)\mathcal O(n^c) ∀c0,log(n)O(nc)因此对数复杂度无限接近于常数
3.多项式复杂度 O ( n c ) \mathcal O(n^c) O(nc)
4.指数复杂度 O ( a n ) \mathcal O(a^n) O(an) 计算成本增长极快通常认为不可以接受
复杂度增长速度
复杂度分析
算法分析的两个主要任务 正确性不变性×单调性 复杂度
C 等高级语言的基本指令均等效于常数条 RAM 的基本指令在渐进意义下两者相当。
复杂度分析的主要方法 1.迭代级数求和 2.递归递归追踪 递推方程
实例冒泡排序
问题给定 n 个整数将它们按非降序排列 观察有序/无序序列中任意/总有一对相邻元素顺序/逆序 思路扫描交换依次比较每一个相邻元素如果必要交换之若整躺扫描都没有进行交换则排序完成否则再做一趟扫描交换。
void bubblesort(int A[],int n){for(bool sorted false; sorted !sorted; n--){ // 逐躺扫描交换直至完全有序for(int i 1; i n; i){ // 自左向右逐对检查A[0,n)内各相邻元素if(A[i-1]A[i]){ // 若逆序则swap(A[i-1], A[i]); //令其互换同时sorted false; //清楚全局有序标志 }}}
}不变性经过 k 轮扫描交换后最大的 k 个元素必然就位 单调性经过 k 轮扫描交换后问题规模缩减至 n-k 正确性经过最多 n 躺扫描后算法必然终止且能正确解答。
迭代与递归
递归跟踪分析检查每个递归实例累计所需时间调用语句本身计入对应的子实例其总和即算法执行时间。
实例数组求和二分递归
int sum(int A[], int lo, int hi){ //区间范围A[lo, hi]if(lo hi) return A[lo]; //base caseint mi (lo hi) 1; //右移一位相当于除以2 只有正数适用而负数不适用return sum(A, lo, mi) sum(A, mi1, hi);
} //入口形式为 sum(A,0,n-1)master theorem 动态规划
实例Fibonacci 序列 F ( 1 ) 1 F ( 2 ) 1 , F ( n ) F ( n − 1 ) F ( n − 2 ) ( n 3 n ∈ N ∗ ) F(1)1F(2)1, F(n)F(n-1)F(n-2)(n3n∈N*) F(1)1F(2)1,F(n)F(n−1)F(n−2)(n3n∈N∗)
计算Fibonacci数列的第n项迭代版O(n)
__int64 fibI ( int n ) { __int64 f 1, g 0; //初始化fib(-1)、fib(0)while ( 0 n-- ) { g f; f g - f; } //依据原始定义通过n次加法和减法计算fib(n)return g; //返回
}计算Fibonacci数列的第n项二分递归版O(2^n)
__int64 fib ( int n ) { return ( 2 n ) ?( __int64 ) n //若到达递归基直接取值: fib ( n - 1 ) fib ( n - 2 ); //否则递归计算前两项其和即为正解
}计算Fibonacci数列第n项线性递归版O(n)
__int64 fib ( int n, __int64 prev ) { //入口形式fib(n, prev)if ( 0 n ) //若到达递归基则{ prev 1; return 0; } //直接取值fib(-1) 1, fib(0) 0else { //否则__int64 prevPrev; prev fib ( n - 1, prevPrev ); //递归计算前两项return prevPrev prev; //其和即为正解}
} //用辅助变量记录前一项返回数列的当前项O(n)//Fib.h
using Rank unsigned int;class Fib { //Fibonacci数列类
private:Rank f, g; //f fib(k - 1), g fib(k)。均为int型很快就会数值溢出
public:Fib ( Rank n ) //初始化为不小于n的最小Fibonacci项{ f 1; g 0; while ( g n ) next(); } //fib(-1), fib(0)O(log_phi(n))时间Rank get() { return g; } //获取当前Fibonacci项O(1)时间Rank next() { g f; f g - f; return g; } //转至下一Fibonacci项O(1)时间Rank prev() { f g - f; g - f; return g; } //转至上一Fibonacci项O(1)时间
};//main.c
#includectime
#includeiostream
using namespace std;#include Fib.h__int64 fibI ( int n ); //迭代版
__int64 fib ( int n ); //二分递归版
__int64 fib ( int n, __int64 f ); //线性递归版int main ( int argc, char* argv[] ) { //测试FIB
// 检查参数if ( 2 argc ) { fprintf ( stderr, Usage: %s Rank\n, argv[0] ); return 1; }int n atoi ( argv[1] );
// 依次计算Fibonacci数列各项printf ( \n------------- class Fib -------------\n );Fib f ( 0 );for ( int i 0; i n; i, f.next() )printf ( fib(%2d) %d\n, i, f.get() );for ( int i 0; i n; i, f.prev() )printf ( fib(%2d) %d\n, n - i, f.get() );printf ( \n------------- Iteration -------------\n );for ( int i 0; i n; i )printf ( fib(%2d) %22I64d\n, i, fibI ( i ) );printf ( \n------------- Linear Recursion -------------\n );for ( int i 0; i n; i ) {__int64 f;printf ( fib(%2d) %22I64d\n, i, fib ( i, f ) );}printf ( \n------------- Binary Recursion -------------\n );for ( int i 0; i n; i )printf ( fib(%2d) %22I64d\n, i, fib ( i ) );return 0;
}实例LCS最长公共子序列
两个字符串中找到最长的子序列这里明确两个含义 1.子串表示连续的一串字符 。 2.子序列表示不连续的一串字符。
1.两个字符串具有相同尾序那么同时去掉两者的尾序不影响它们的距离 2.如果 A 和 B 是不同的符号 ( A ≠ B A≠B AB)则 L C S ( X A , Y B ) LCS(X^A,Y^B) LCS(XA,YB) 是以下两者的最大者 L C S ( X A , Y ) , L C S ( X , Y B ) LCS(X^A,Y), LCS(X,Y ^B) LCS(XA,Y),LCS(X,YB) 适用于所有字符串 X 、 Y X、Y X、Y
给定两个字符串S1和S2我们需要找到一个最长的子序列该子序列同时出现在S1和S2中。这个子序列不要求在原字符串中是连续的但在原字符串中的相对顺序必须与原字符串中的顺序相同。
举例说明
假设有两个字符串 S1 “ABCBDAB” S2 “BDCAB”
它们的一个最长公共子序列是BCAB它在两个字符串中都出现而且是最长的。
LCS问题的目标是找到这个最长的公共子序列的长度以及可能的子序列之一。在动态规划中可以使用一个二维表格来解决这个问题表格中的值表示两个字符串在不同位置的字符之间的LCS长度。
通过解决LCS问题我们可以解决许多实际应用如文本比对、版本控制、DNA序列比对等。这个问题在算法设计和字符串处理中具有重要性。
#include iostream
#include vector
#include stringusing namespace std;string longestCommonSubsequence(string s1, string s2) {int m s1.length();int n s2.length();// 创建DP表初始化为0vectorvectorint dp(m 1, vectorint(n 1, 0));// 填充DP表for (int i 1; i m; i) {for (int j 1; j n; j) {if (s1[i - 1] s2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;} else {dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}}// 回溯构建最长公共子序列string lcs ;int i m, j n;while (i 0 j 0) {if (s1[i - 1] s2[j - 1]) {lcs s1[i - 1] lcs;i--;j--;} else if (dp[i - 1][j] dp[i][j - 1]) {i--;} else {j--;}}return lcs;
}int main() {string s1 ABCBDAB;string s2 BDCAB;string result longestCommonSubsequence(s1, s2);cout Longest Common Subsequence: result endl;return 0;
}
