set<int> s;
s.insert(1);
s.insert(2);
...
s.insert(n);
I wonder how much time it takes for s.find(k) where k is a number from 1..n?
I assume it is log(n). Is it correct?
views:
199answers:
2
+7
A:
O( log N ) to search for an individual element.
§23.1.2 Table 69
expression return note complexity
a.find(k) iterator; returns an iterator pointing to an logarithmic
const_iterator element with the key equivalent to k,
for constant a or a.end() if such an element is not
found
David Rodríguez - dribeas
2010-05-07 19:01:27
A:
ok never mind. I found it on the internet. it is nlog(n). http://www.cplusplus.com/reference/stl/set/find/
I'm trying to think in practice, when is good to use set? for most of the time, I think vector and map can be able to do the job. Does anybody have any idea?
tsubasa
2010-05-07 19:01:32
This is wrong. That page itself says "logarithmic in size" which is to say O(log n). **Not** O(n log n). Also, be careful about that site; while it's pretty complete it does have some mis-information.
GMan
2010-05-07 19:06:42
Just so there's no confusion, finding a **single** element is `O(log n)`. Finding all `n` is `O(n log n)`. A set is much better if you need faster worst-case insertions, deletions and searches.
IVlad
2010-05-07 19:07:15
A map is a set with a key and a value, whereas the set is only a key. A lookup in a map is O(log n), not O(n log n), and a vector search is linear. So if you have 1000 items in a set/map it will take, on average, 33 comparisons, whereas a vector search will take, on average, 500 comparisons.
Joel
2010-05-07 19:07:15
Logarithmic means `O( log N )`, not `O( N log N )`. If you want to ask something else, ask another question. (Or better search for it, it most probably has been asked before)
David Rodríguez - dribeas
2010-05-07 19:08:58
I think the downvoters are jumping the gun here. The OP asked `wonder how much time it takes for s.find(k) where k is a number from 1..n? I assume it is nlog(n). Is it correct?`. He said `k` is **from 1 to n**, not between, so he probably meant doing it for all values of `k`.
IVlad
2010-05-07 19:10:32
@IVlad: 'finding all n' can be confusing. Iterating over all elements in the set takes linear time. It is performing N searches takes `N O( log N )` or `O( N log N )`
David Rodríguez - dribeas
2010-05-07 19:11:16
I don't think it would be phrased that way. Certainly you would say **for all** k from 1 to n? Either way, a correct answer would point out that each lookup takes O(log n) as to be unambiguous.
rlbond
2010-05-07 19:12:22
@joel: how do you come to 33 comparisons? log2(1000) = 10, not 33. The average case will even be a little bit lower than 10.
KillianDS
2010-05-07 19:13:43
@IVlad: And if it is for all k from 1 to n, then the answer is linear time `O( N )`, transversing a set in order takes linear time (basically for each edge in the tree you transverse it twice, once going down, then again going up)
David Rodríguez - dribeas
2010-05-07 19:14:34
@David - not if you use the `find` method. I agree that the question is badly phrased though.
IVlad
2010-05-07 19:27:32
Bah, you are correct. My apologies. Still an order of magnitude less than 500
Joel
2010-05-07 19:31:07
@joel: in reality, the worst case will typically be about 1 *greater* than the base 2 logarithm -- in a normal case, the tree won't be perfectly balanced. A typical "balanced" tree like AVL or R-B will allow a one sub-tree to be roughly 1 higher than the other.
Jerry Coffin
2010-05-07 22:49:20
Actually, a RB tree allows the path length to get twice as long as the shortest path. However. the point is the orders of magnitude, not the exact numbers.
Joel
2010-05-08 03:24:21