算法调查数组中的第k个下一个元素 [英] Algorithm-finding kth next element in an array

问题描述

我解决不了的问题可以请你帮忙吗？

I couldn't solve a question can you please help?

For i=1 to i=n/2, if A[i]<=A[2i] and A[i]<=A[2i+1] A is called as a "bst" 

什么是寻找在第k 最小元素的时间复杂度 BST n个元素？

What's the time complexity for finding kth smallest element in a bst with n elements?

推荐答案

首先，你的意思是堆，而不是BST（您所描述的数据结构必然是一个堆和不一定是BST）。

First, you mean "heap", not "bst" (the data structure you described is necessarily a heap and is not necessarily a bst).

二，这都不明显，这个问题是在O（K）可解时间 - 但直到1992年的弗雷德里克森给了一个O（K） - 时间算法，这个。我没有读过本文通过所有的方式，但它是18页的复杂的技术参数，我惊呆了奥运会组织者希望学生基本上是从头拿出吧！ （或者，也许他们希望他们已经熟悉的算法 - 在这种情况下，我要说的是，（一），它仍然要求颇多，和（b）这不是一个很好的问题）

Second, it's not at all obvious that this problem is solvable in O(k) time -- it was not until 1992 that Frederickson gave an O(k)-time algorithm for this. I haven't read this paper all the way through, but it's 18 pages of intricate technical argument, and I'm flabbergasted that Olympiad organisers would expect students to essentially come up with it from scratch! (Or perhaps they expect them to already be familiar with the algorithm -- in which case I would say that (a) it's still asking quite a lot, and (b) it's not a very good question.)

这篇关于算法调查数组中的第k个下一个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！