Improve algorithm speed.

Sep 30, 2021 at 8:48am
Input:
1
2
3
    T is a positive-number sorted array in ascending order and the numbers are unique, T is a subset of  {1,2,3,...,511}. 

    k is a positve number and k <= |T|


Label the numbers from 1 to 511 in a perfect binary tree:
1
2
3
4
                  1
              2       3
          4     5   6    7
     .............................


You can open the picture if you can not imagine what the tree looks like.

https://gitee.com/wuzhenhai1/my-cdn/raw/master/xxx.PNG


Now try to find the first occurrence of the following number set(S) in T:
1) T[0](the first number in T) must be in S
2) try to use the small numbers as much as possible
3) k = |S|
4) if (x,y) is in S, then x is not the ancestor of y and y is not the ancestor of x in the tree.

I develop an top-to-down recursive algorithm, but it is too slow when there are more than 200 elements.
Last edited on Oct 2, 2021 at 3:18am
Oct 1, 2021 at 10:13pm
In case this matters to your attempt, the tree you show is not correct.

The 1, 2, 3 and 4 wouldn't be on this positions, for example.

1 would be the far leftmost entry or leaf.

The root might be, in a balanced tree that includes data from 1 to 511 inclusive, something closer to 260.

I may not understand what you're doing or asking, though...we see no code.

A balanced height binary tree will perform reasonably well with data beyond several thousand entries, but then "slow" is relative to expectations.
Last edited on Oct 1, 2021 at 10:16pm
Oct 1, 2021 at 11:55pm
The tree is right.

The illustrated tree is only used for the forth constraint.

There are at most 511 numbers.
Oct 2, 2021 at 12:45am
I feel like I am not understanding the rules.
1 can't be in the table -- is ancestor of everything except itself.
rules say 1 must be in table.
unless T[0] means something else.
Oct 2, 2021 at 2:08am
1 may not be in T.
T only picks partial numbers in the tree.
 
     T belongs to {1,2,3,...,511}.
Last edited on Oct 2, 2021 at 2:09am
Oct 2, 2021 at 2:35am
"The tree is right."

Then either those aren't values in the tree (and I have no idea what those numbers are if they are not values in the tree), or...it isn't a binary tree - not by the classic meaning of that term.

What is it?

If you say it is a binary tree, there are no binary tree algorithms that could search that tree if this lists the values of the leaves. The tree could be traversed, by the standard binary tree algorithms would not list the values in order.

Maybe it is being called a binary tree in the context of your work or study, but it isn't a standard definition. It may be a kind of directed graph or some other data structure.

This looks like the numbers of blocks in a pyramid...well, one side of it or just a triangle if this is 2d (and not necessarily square blocks or tiles), which is the layout of a geometric structure.

Can you show any code?
Last edited on Oct 2, 2021 at 2:42am
Oct 2, 2021 at 3:08am
Ouch.

You can open the picture if you can not imagine.

https://gitee.com/wuzhenhai1/my-cdn/raw/master/xxx.PNG

A simple view is that:
select k numbers from T and there are 4 constraints. The constraints have already been introduced.
Last edited on Oct 2, 2021 at 3:15am
Oct 2, 2021 at 3:30am
@Niccolo
Wu zhen hai's use of terminology is correct. What's depicted is a perfect (albeit truncated) binary tree. It's just not a binary search tree.

@Wu zhen hai
We don't know what algorithm you're using nor how you implemented it. Showing the code that's "too slow" would help us help you immensely.

-Albatross
Oct 2, 2021 at 3:43am
My implementation is almost a violent enumeration.

I need a smarter algorithm.

Or there is only one stupid algorithm, no smarter algorithm.
Last edited on Oct 2, 2021 at 3:46am
Topic archived. No new replies allowed.