数据结构和算法(1):开始

这篇具有很好参考价值的文章主要介绍了数据结构和算法(1):开始。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法概述

所谓算法,即特定计算模型下,旨在解决特定问题的指令序列
输入 待处理的信息(问题)
输出 经处理的信息(答案)
正确性 的确可以解决指定的问题
确定性 任一算法都可以描述为一个由基本操作组成的序列
可行性 每一基本操作都可实现,且在常数时间内完成
有穷性 对于任何输入,经有穷次基本操作,都可以得到输出

程序未必是算法,例如发生死循环或者栈溢出时。

算法在满足基本要求时,最重要的是:速度尽可能快,存储空间尽可能少(效率)

计算模型

两个主要方面:
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 c>0,n\gg 2, T(n)<c\cdot f(n) T(n)=O(f(n)) if  c>0,n2,T(n)<cf(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^a+n^b)=\mathcal O(n^a),a>b>0 O(na+nb)=O(na)a>b>0
数据结构和算法(1):开始,数据结构和算法,算法,数据结构
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 c>0,log(n)=\mathcal O(n^c) c>0,log(n)=O(nc),因此对数复杂度无限接近于常数

3.多项式复杂度: O ( n c ) \mathcal O(n^c) O(nc)

4.指数复杂度: O ( a n ) \mathcal O(a^n) O(an)
计算成本增长极快,通常认为不可以接受

复杂度增长速度
数据结构和算法(1):开始,数据结构和算法,算法,数据结构

复杂度分析

算法分析的两个主要任务 = 正确性(不变性×单调性) + 复杂度

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 case
	int mi = (lo + hi) >> 1;	//右移一位,相当于除以2 只有正数适用,而负数不适用
	return sum(A, lo, mi) + sum(A, mi+1, hi);
}	//入口形式为 sum(A,0,n-1)

master theorem

数据结构和算法(1):开始,数据结构和算法,算法,数据结构

动态规划

实例:Fibonacci 序列

F ( 1 ) = 1 , F ( 2 ) = 1 , F ( n ) = F ( n − 1 ) + F ( n − 2 ) ( n > = 3 , n ∈ N ∗ ) 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(n1)+F(n2)(n>=3nN)

计算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) = 0
   else { //否则
      __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
#include<ctime>
#include<iostream>
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 A=B),则 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 XY

给定两个字符串S1和S2,我们需要找到一个最长的子序列,该子序列同时出现在S1和S2中。这个子序列不要求在原字符串中是连续的,但在原字符串中的相对顺序必须与原字符串中的顺序相同。

举例说明:

假设有两个字符串:
S1 = “ABCBDAB”
S2 = “BDCAB”

它们的一个最长公共子序列是"BCAB",它在两个字符串中都出现,而且是最长的。

LCS问题的目标是找到这个最长的公共子序列的长度以及可能的子序列之一。在动态规划中,可以使用一个二维表格来解决这个问题,表格中的值表示两个字符串在不同位置的字符之间的LCS长度。

通过解决LCS问题,我们可以解决许多实际应用,如文本比对、版本控制、DNA序列比对等。这个问题在算法设计和字符串处理中具有重要性。文章来源地址https://www.toymoban.com/news/detail-693883.html

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string longestCommonSubsequence(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    
    // 创建DP表,初始化为0
    vector<vector<int>> dp(m + 1, vector<int>(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;
}

到了这里,关于数据结构和算法(1):开始的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【从零开始学习数据结构 | 第一篇】树

    目录 前言:  树: 树结点之间的关系描述:  树的常见属性: 森林: ​编辑树的性质: 总结: 当谈论数据结构时,树(Tree)是一种极为重要且常用的数据结构之一。树的概念源自现实生活中的树木,它具有分层结构,由 节点(Node) 和 边(Edge) 组成,形成了一种类似于

    2024年04月16日
    浏览(49)
  • 从零开始学习数据结构—【链表】—【探索环形链的设计之美】

    双向环形链表带哨兵,这个时候的 哨兵 , 可以当头,也可做尾 带哨兵双向循环链表:结构稍微复杂,实现简单。一般用来单独存储数据,实际中使用的链表数据结构都是带头双向链表。另外,这个结构虽然结构复杂,但是使用代码实现后会发现结构会带来很多优势。 双向

    2024年02月22日
    浏览(40)
  • 【从零开始学习Redis | 第八篇】认识Redis底层数据结构(下)

    目录 前言:   ZipList: Ziplist的特性: QucikList: QuicList特征: SkipList: 跳表特征: RedisObijct:  小心得: 总结:           在现代软件开发中,数据存储和处理是至关重要的一环。为了高效地管理数据,并实现快速的读写操作,各种数据库技术应运而生。其中,Redis作为一种

    2024年04月12日
    浏览(50)
  • 从0开始学C++ 第二十八课 数据结构深入 - 栈和队列

    第二十八课:数据结构深入 - 栈和队列 学习目标: 理解栈(Stack)的基本概念和特性。 掌握队列(Queue)的基本概念和特性。 学会在C++中使用栈和队列。 了解栈和队列的典型应用场景。 学习内容: 栈(Stack) 概念:栈是一种后进先出(LIFO, Last In First Out)的数据结构,元素

    2024年01月23日
    浏览(45)
  • 从0开始学C++ 第二十七课 数据结构入门 - 数组与链表

    第二十七课:数据结构入门 - 数组与链表 学习目标: 理解数组的基本概念和操作。 掌握链表的基本结构与特点。 学会在C++中定义和操作数组和链表。 了解数组和链表的基本使用场景。 学习内容: 数组(Array) 概念:数组是一种线性数据结构,用一段连续的内存空间来存储

    2024年01月23日
    浏览(47)
  • 【从零开始拿捏数据结构】 顺序表是什么?它有什么样的特性?结构到底是什么样的?

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 数据结构解析 🌄 莫道桑榆晚,为霞尚满天! ​ 什么是数据结构?我们为什么要学数据结构?数据结构中的顺序表长什么样子?它是怎么运用? ​ 本期我们将对这些一一讲解,彻底明白数据结构的重要性,以及顺序表是一种什么的数据

    2024年02月08日
    浏览(102)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(49)
  • 【算法与数据结构】--算法应用--算法和数据结构的案例研究

    一、项目管理中的算法应用 在项目管理中,算法和数据结构的应用涉及项目进度、资源分配、风险管理等方面。以下是一些案例研究,展示了算法在项目管理中的实际应用: 项目进度管理 : 甘特图算法 :甘特图是一种项目进度管理工具,它使用甘特图算法来展示项目任务

    2024年02月08日
    浏览(55)
  • 数据结构与算法设计分析—— 数据结构及常用算法

    1、顺序表与链表 线性表是 线性结构 ,是包含n个数据元素的有限序列,通过顺序存储的线性表称为 顺序表 ,它是将线性表中所有元素按照其逻辑顺序,依次存储到指定存储位置开始的一块连续的存储空间里;而通过链式存储的 链表 中,每个结点不仅包含该元素的信息,还

    2024年02月07日
    浏览(59)
  • 数据结构和算法——数据结构

    目录 线性结构  队列结构的队列 链表结构的队列 链表的面试题 单向链表应用场景 约瑟夫环问题 栈结构 中缀表达式 前缀表达式 后缀表达式 非线性结构 图 递归解决迷宫问题 递归解决八皇后问题 顺序存储方式,顺序表 常见的顺序存储结构有:数组、队列、链表、栈 链式存

    2024年02月07日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包