0%

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列\(\lbrace2, 1, 3\rbrace\)\(\lbrace2, 3, 1\rbrace\)插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。

阅读全文 »

最大子列和问题,即给定N个整数的序列\(\{A_1,A_2,\ldots,A_N \}\),求函数\(f(i,j)=max\lbrace 0,\sum\limits_{i=0}^n{A_k}\rbrace\)的最大值。 例如\(\lbrace-2,11,-4,13,-5,-2\rbrace\)的最大子列和为20,子列为\(\lbrace11,-4,13\rbrace\). \(\lbrace-10, 1, 2, 3, 4, -5, -23, 3, 7, -21\rbrace\)的最大子列和为10,子列为\(\lbrace1,2,3,4\rbrace\)

阅读全文 »

  最简单的矩阵乘法可以通过三重循环来实现,其时间复杂度为\(\Theta(n^{3})\),Strassen算法通过巧妙的增加加法来减少乘法实现了\(O(n^{2.81})\)的时间复杂度

阅读全文 »

选择排序是一种很容易理解和实现的简单排序算法。

阅读全文 »

插入排序的平均时间复杂度是\(O(n^2)\),对于少量元素的排序,是个有效的算法

阅读全文 »