n次执行O（h）算法的时间复杂度
做O（h）算法的时间复杂度是多少？当h是节点的高度，以BST n倍为单位（树中的元素数），我相信是O（n），而不是O（n*h），但我不知道如何证明它。
在O（h）中工作的特定算法是在BST中查找元素的顺序前体。
共有2个答案
O（n²）。
二叉查找树是不平衡的，这意味着节点的高度可以等于树的节点数，因此为O（n²）。
在任何BST中计算n次有序后继数的成本为O（n）。要看到这一点，请计算您触摸树中每条边的次数。您将在第一次探索子树时传递一次边缘，在离开子树后再次传递。总的来说，这意味着每个边最多接触两次，因此完成的总功为O（n）。
请注意，一般来说，您可以在高度h为O（hn）的BST上执行n O（h）时间的成本上限，这永远不会低估事情。然而，如果您更具体地了解所使用的算法，就像在本例中一样，您可以得到一个更严格的界限。
-
查找p的伪码算法为： 假设我有一个int值的数组H[1到m]，其中“p”是峰值元素，如果： 基本上，如果H【p】大于或等于其相邻元素，则H【p】为峰值。 假设数组H在开始和结束时都大于1个元素，数组为H[0到m 1]，其中H[0]=H[m 1]=无穷大。因此，H[0]和H[m 1]是哨兵。然后是元素p，其中1≤ p≤ n、 是一个峰值，如果H【p-1】≤ H【p】≥ H【p 1】。 我认为渐近时间
-
给定一个整数数组arr，计算元素x，使得x 1也在arr中。如果arr中有重复项，请分别计数。 示例1：输入：arr=[1,2,3]输出：2说明：1和2被计数，因为2和3在arr中。 示例2：输入：arr=[1,1,2]输出：2解释：1计数两次，原因2在arr中。 示例3：输入：arr=[1,1,3,3,5,5,7,7]输出：0说明：没有计算数字，因为arr中没有2、4、6或8。 示例4：输入：a
-
描述一个O（n logn）-时间算法，给定一组由n个整数和另一个整数x组成的S，该算法确定S中是否存在两个元素，其和正好是x。 我计划用二进制搜索来搜索这个。 我如何找到这个算法的时间复杂度？如果T（n）不是（n log n），正确的算法是什么？
-
我试图为这段代码找出一个大O的紧密界限： 如果我们从内最循环开始，它将在最坏的情况下运行k=n^2次，占O（N^2）。如果语句每次j=m*i时都为真，其中m是一个任意常数。由于j从1运行到i^2，这将在m={1,2，...，i}时发生，这意味着它将在i次时为真，i最多可以是n，所以最坏的情况将是m={1,2，...，n}=n次。如果i=n，第二个循环应该有O（N^2）的最坏情况。外环具有O（N）的
-
问题内容： 这是第 5章破解编码面试中的问题9.4 问题： 编写一种方法以返回集合的所有子集。 这是我用Java编写的解决方案（经过测试，它可以正常工作!!!） 我看了这个问题的解决方案，作者说该算法的解决方案以 _O（2 n）_时间复杂度和 _O（2 n）_空间复杂度运行。我同意她的观点，该算法运行时间为 _O（2 n），_因为要解决此问题，您必须考虑以下事实：对于任何元素，您都有两种可能性，它