小编joh*_*ohn的帖子

二进制搜索树对具有二分搜索的排序数组有什么好处？只是通过数学分析我没有看到差异,所以我假设低级实现开销必须存在差异.平均病例运行时间的分析如下所示.

使用二进制搜索
搜索的排序数组:O(log(n))
插入:O(log(n))(我们运行二进制搜索以查找插入元素的位置)
删除:O(log(n))(我们运行二进制搜索找到要删除的元素)

二进制搜索树
搜索:O(log(n))
插入:O(log(n))
删除:O(log(n))

对于上面列出的操作,二进制搜索树具有最坏的O(n)情况(如果树不平衡),所以这看起来实际上比使用二进制搜索的排序数组更差.

另外,我不假设我们必须预先对数组进行排序(这将花费O(nlog(n)),我们将逐个插入元素到数组中,就像我们对二叉树所做的那样.唯一的好处BST我可以看到它支持其他类型的遍历,如inorder,preorder,postorder.

我在网上找到了一个链接,显示了生成字符串所有组合的算法:http://www.mytechinterviews.com/combinations-of-a-string

算法复制如下.

void combine(String instr, StringBuffer outstr, int index)
{
    for (int i = index; i < instr.length(); i++)
    {
        outstr.append(instr.charAt(i));
        System.out.println(outstr);
        combine(instr, outstr, i + 1);
        outstr.deleteCharAt(outstr.length() - 1);
    }
} 

combine("abc", new StringBuffer(), 0);

我不明白的是这条线:

outstr.deleteCharAt(outstr.length() - 1);

如果我删除这一行,该程序显然不再起作用,但为什么首先需要它？我理解递归的想法,我们改变一个初始字符并递归剩余的字符,但deleteChar行似乎在逻辑上不适合任何地方.添加outstr.deleteCharAt行的原因是什么？

我正在使用性能较慢的Oracle数据库,因为在某些表上连接以获得结果.我正在考虑创建一个存储这些数据的新表,以便可以快速检索它而无需执行连接.另一种方法是为我正在执行的连接创建一个视图,然后始终查询视图以获取数据.使用新表与创建视图之间的性能折衷是什么？我认为一个视图仍然需要运行连接,因此它不会提供与新表一样好的性能.

有关Oracle数据库视图的信息,请访问:http://docs.oracle.com/cd/B19306_01/server.102/b14200/statements_8004.htm - Oracle中的View是什么？

根据以下回复进行澄清.查询大部分已经过优化,因此我不想进行优化.更喜欢新表或物化视图,但想知道哪个可能更好.我对表演很感兴趣.编写更多代码以使新表与旧表保持同步不是问题.我只会在对旧表进行修改的地方添加修改语句.如果它比添加新表慢,我不想使用物化视图.

不同之处在于数据刷新对于物化视图还是新表更有效.对于新表,基本上我将在旧表更新的地方添加更新语句.因此,当用户查询新表时,数据已经存在(不需要进一步处理).但是对于物化视图,如果视图仅在用户查询视图时刷新自身,那么这可能会更慢.

深度优先搜索似乎能够执行与访客设计模式相似的功能。访问者允许您定义一些数据结构并根据需要在这些结构上添加操作（以多个访问者的形式），而无需修改结构本身。维基百科上提供了访客模式的描述。如果我们在数据结构上进行深度优先搜索（或其他任何图形搜索算法，例如广度优先搜索），并且每次找到该结构的元素，我们都会运行所需的操作，那么这似乎执行与访客。例如，考虑一棵树。即使树的某些节点具有不同的类型，我们在执行DFS时仍然可以检查节点类型，然后根据节点类型执行不同的操作。