已知序列X={x1,x2,…,xm},序列Y={y1,y2,…,yn},使用动态规划算法求解序列X和Y的最长公共子序列,其最坏时间复杂度为()。A、O(m*n)B、O(m+n)C、O(m*2n)D、O(n*2m)

已知序列X={x1,x2,…,xm},序列Y={y1,y2,…,yn},使用动态规划算法求解序列X和Y的最长公共子序列,其最坏时间复杂度为()。

  • A、O(m*n)
  • B、O(m+n)
  • C、O(m*2n
  • D、O(n*2m

相关考题:

对n个记录的序列进行堆排序,最坏情况下的时间复杂度为______。 A、O(logn)B、O(nlogn)C、O(n)D、O(n^2)

下面程序段的时间复杂度为( )。for (i=0; ifor (j=0; jA[i][j]=i*j; A. O (m2)B. O (n2)C. O (m*n)D. O (m+n)

下面程序段的时间复杂度是()。for(i=0;in;i++)for(j=1;jm;j++)A[i][j]=0; A、O(n)B、O(m+n+1)C、O(m+n)D、O(m*n)

将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为() A、O(m+n)B、O(n)C、O(m)D、O(1)

使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为()A.O(N)B.O(logN)C.O(N*N)D.O(N*logN)

下面程序段的时间复杂度是()。for(j=0;jfor(k=0;ka[j][k]=j*k; A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)

下面程序段的时间复杂度是()。s=0;for(i=0;ifor(j=0;js+=B[i][j];sum=s; A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)

阅读下列函数说明和C代码,填入(n)处。[说明]以下C语言程序实现了生成从里到外是连续的自然数排列的回旋矩阵,矩阵形式如下:7 6 5 168 1 4 159 2 3 1410 11 12 13程序的变量说明如下:x1:矩阵上边界;x2:矩阵下边界;y1:矩阵左边界;y2:矩阵右边界;s:数组元素升降标记,s等于1为升,s等于-1为降;a[]:存放矩阵元素的数组。仔细阅读C语言程序源码,将(n)处的语句补充完整。(注:每处仅一个语句)[C程序]include<stdio.h>void main ( ){const int N=20;int i=0,j=0,a[N][N],n;int m,x1,x2,y1,y2,s;while (1){Printf ("\ninput matrix row N( N>=2): ");scanf ("%d",n);printf ("\n");if (n>=2)break;}m=n*n;x1=0; y1=0; x2=n; y2=n;if(n%2==0){j=n-1; y2=n-1; s=1;}else{i=n-1; y1=1; s=-1; }while (1){if (s==1){for (i; i<x2; i++) a[i][j]=m--;i--;j--;(1)for (j;j>=y1;j--) a[i][j]=m--;j++;i--;y1++;(2)}else{for (i;i>=x1;i--)a[i][j]=m--;i++;j++;(3)for (j;j<y2;j++)(4)(5)i++;(6)S=i;}if (m<1) break;}for (i=O;i<n; i++){for (j=O;j<n;j++)printf ("%6d",a[i][j]);printf ("\n");}printf ("\n");}

将长度为n的单链表链接到长度为m的单链表之后的算法的时间复杂度是()。 A.O(1)B.O(n)C.O(m)D.O(m+n)

下面程序段的时间复杂度为 ( ) for(i=0;i<m;i++) for(j=0;j<n;j++) A[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)

对长度为n的关键字序列进行堆排序的空间复杂度为 ( )A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)

用快速排序的方法对包含n个关键字的序列进行排序,最坏情况下执行的时间为A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)

下面算法是实现对n个整数的序列进行选择排序,其中序列的“长度”n为问题的规模。该算法的时间复杂度为(11)。 void select_sort(int a[],int n){ //将a中整数序列重新排列成从小到大有序的整数序列 for(i=0;i<n-1;++i){ j=i; for(k=i+1;k<n;++k)if(a[k]<a[j])j=k; if(j!=i){w=a[j];a[j];a[i];a[i]=w} )//select_sortA.O(n2)B.O(n3)C.O(n4)D.O(n)

对于求取两个长度为n的字符串的最长公共子序列问题,利用(41)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。A.贪心B.分治C.分支-限界D.动态规划

对n个关键字的序列进行快速排序,平均情况下的空间复杂度为_______A.O(1)B.O(logn)C.O(n)D.O(nlogn)

对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(24)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。串 <1,0,0,1,O,1,0,1>和<0,1,0,1,1,0,1,1>的最长公共子序列的长度为(25)。A.分治B.贪心C.动态规划D.分支—限界

在二维数组M[0...n,0...m]中,访问某个元素的平均时间复杂度为______。A.O(1)B.O(nm)C.O(m+n)D.O(nn)

求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为( )。经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j],如下式所示。采用自底向上的方法实现该算法,则时间复杂度为(请作答此空)A.O(n^2)B.O(n^21gn)C.O(n^3)D.O(n2^n)

将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为()。A.O(n)B.0(1)C.O(m)D.O(m+n)

将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为()。A、O(1)B、O(n)C、O(m)D、O(m+n)

下面程序的时间复杂度为()。 for(i=0;iA、O(m2)B、O(n2)C、O(m×n)D、O(m+n)

给定一个由n个数组成的序列,要求该序列的最长单调上升子序列,请设计对应的算法并分析其时间复杂度,如果时间复杂度劣于O(nlogn)的,将其优化为O(nlogn)时间复杂度的算法。

下面程序的时间复杂度为()。 for(i=0;iA、O(m×n×t)B、O(m+n+t)C、O(m+n×t)D、O(m×t+n)

若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X和Y的一个最长公共子序列:()

判断题我(wǒ)喜欢(xǐhuān)猫(māo),但是(dànshì)丈夫(zhàngfu)小(xiǎo)喜欢(xǐhuān),所以(suǒyǐ)到(dào)现在(xiànzài)家里(jieli)也(yě)没有(méiyǒu)猫(māo)。我(wǒ)希望(xīwàng)有一天(yǒuyītiān)能(néng)有(yǒu)一(yī)个(gè)小(xiǎo)猫(māo)。★我(wǒ)丈夫(zhàngfu)想(xiǎng)要(yào)一(yī)个(gè)小(xiǎo)猫(māo)。(  )A对B错

单选题已知序列X={x1,x2,…,xm},序列Y={y1,y2,…,yn},使用动态规划算法求解序列X和Y的最长公共子序列,其最坏时间复杂度为()。AO(m*n)BO(m+n)CO(m*2n)DO(n*2m)

问答题给定一个由n个数组成的序列,要求该序列的最长单调上升子序列,请设计对应的算法并分析其时间复杂度,如果时间复杂度劣于O(nlogn)的,将其优化为O(nlogn)时间复杂度的算法。