1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Complexity</title> 5<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../index.html" title="Chapter 1. Boost.Icl"> 8<link rel="up" href="../implementation.html" title="Implementation"> 9<link rel="prev" href="../implementation.html" title="Implementation"> 10<link rel="next" href="inplace_and_infix_operators.html" title="Inplace and infix operators"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="../implementation.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../implementation.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="inplace_and_infix_operators.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h3 class="title"> 27<a name="boost_icl.implementation.complexity"></a><a class="link" href="complexity.html" title="Complexity">Complexity</a> 28</h3></div></div></div> 29<h5> 30<a name="boost_icl.implementation.complexity.h0"></a> 31 <span class="phrase"><a name="boost_icl.implementation.complexity.complexity_of_element_containers"></a></span><a class="link" href="complexity.html#boost_icl.implementation.complexity.complexity_of_element_containers">Complexity 32 of element containers</a> 33 </h5> 34<p> 35 Since <span class="emphasis"><em>element containers</em></span> <a href="http://www.cplusplus.com/reference/stl/set/" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span></code> 36 </a> and <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code> are only 37 extensions of stl::set and stl::map, their complexity characteristics are 38 accordingly. So their major operations insertion (addition), deletion and 39 search are all using logarithmic time. 40 </p> 41<h5> 42<a name="boost_icl.implementation.complexity.h1"></a> 43 <span class="phrase"><a name="boost_icl.implementation.complexity.complexity_of_interval_containers"></a></span><a class="link" href="complexity.html#boost_icl.implementation.complexity.complexity_of_interval_containers">Complexity 44 of interval containers</a> 45 </h5> 46<p> 47 The operations on <span class="emphasis"><em>interval containers</em></span> behave differently 48 due to the fact that intervals unlike elements can overlap any number of 49 other intervals in a container. As long as intervals are relatively small 50 or just singleton, interval containers behave like containers of elements. 51 For large intervals however time consumption of operations on interval containers 52 may be worse, because most or all intervals of a container may have to be 53 visited. As an example, time complexity of <a class="link" href="../function_reference/addition.html" title="Addition"><span class="emphasis"><em><span class="bold"><strong>Addition</strong></span></em></span></a> on interval containers 54 is briefly discussed. 55 </p> 56<p> 57 More information on <span class="emphasis"><em><span class="bold"><strong>complexity characteristics</strong></span></em></span> 58 of <span class="bold"><strong>icl's</strong></span> functions is contained in section 59 <a class="link" href="../function_reference.html" title="Function Reference">Function Reference</a> 60 </p> 61<h6> 62<a name="boost_icl.implementation.complexity.h2"></a> 63 <span class="phrase"><a name="boost_icl.implementation.complexity.time_complexity_of_addition"></a></span><a class="link" href="complexity.html#boost_icl.implementation.complexity.time_complexity_of_addition">Time 64 Complexity of Addition</a> 65 </h6> 66<p> 67 The next table gives the time complexities for the overloaded <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+=</span></code> 68 on interval containers. The instance types of <code class="computeroutput"><span class="identifier">T</span></code> 69 are given as column headers. Instances of type parameter <code class="computeroutput"><span class="identifier">P</span></code> 70 are denoted in the second column. The third column contains the specific 71 kind of complexity statement. If column three is empty <span class="emphasis"><em><span class="bold"><strong>worst case</strong></span></em></span> complexity is given in the related 72 row. 73 </p> 74<div class="table"> 75<a name="boost_icl.implementation.complexity.t0"></a><p class="title"><b>Table 1.15. Time Complexity of Addition:</b></p> 76<div class="table-contents"><table class="table" summary="Time Complexity of Addition:"> 77<colgroup> 78<col> 79<col> 80<col> 81<col> 82<col> 83<col> 84<col> 85<col> 86</colgroup> 87<thead><tr> 88<th> 89 </th> 90<th> 91 <p> 92 <code class="computeroutput"><span class="identifier">P</span></code> 93 </p> 94 </th> 95<th> 96 </th> 97<th> 98 <p> 99 interval<br> set 100 </p> 101 </th> 102<th> 103 <p> 104 separate<br> interval<br> set 105 </p> 106 </th> 107<th> 108 <p> 109 split<br> interval<br> set 110 </p> 111 </th> 112<th> 113 <p> 114 interval<br> map 115 </p> 116 </th> 117<th> 118 <p> 119 split<br> interval<br> map 120 </p> 121 </th> 122</tr></thead> 123<tbody> 124<tr> 125<td> 126 <p> 127 <code class="computeroutput"><span class="identifier">T</span><span class="special">&</span> 128 <span class="keyword">operator</span> <span class="special">+=(</span><span class="identifier">T</span><span class="special">&</span> 129 <span class="identifier">object</span><span class="special">,</span> 130 <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&</span> <span class="identifier">addend</span><span class="special">)</span></code> 131 </p> 132 </td> 133<td> 134 <p> 135 <code class="computeroutput"><span class="identifier">T</span><span class="special">::</span><span class="identifier">element_type</span></code> 136 </p> 137 </td> 138<td> 139 </td> 140<td> 141 <p> 142 <span class="emphasis"><em>O(log n)</em></span> 143 </p> 144 </td> 145<td> 146 <p> 147 <span class="emphasis"><em>O(log n)</em></span> 148 </p> 149 </td> 150<td> 151 <p> 152 <span class="emphasis"><em>O(log n)</em></span> 153 </p> 154 </td> 155<td> 156 <p> 157 <span class="emphasis"><em>O(log n)</em></span> 158 </p> 159 </td> 160<td> 161 <p> 162 <span class="emphasis"><em>O(log n)</em></span> 163 </p> 164 </td> 165</tr> 166<tr> 167<td> 168 </td> 169<td> 170 <p> 171 <code class="computeroutput"><span class="identifier">T</span><span class="special">::</span><span class="identifier">segment_type</span></code> 172 </p> 173 </td> 174<td> 175 <p> 176 best case 177 </p> 178 </td> 179<td> 180 <p> 181 <span class="emphasis"><em>O(log n)</em></span> 182 </p> 183 </td> 184<td> 185 <p> 186 <span class="emphasis"><em>O(log n)</em></span> 187 </p> 188 </td> 189<td> 190 <p> 191 <span class="emphasis"><em>O(log n)</em></span> 192 </p> 193 </td> 194<td> 195 <p> 196 <span class="emphasis"><em>O(log n)</em></span> 197 </p> 198 </td> 199<td> 200 <p> 201 <span class="emphasis"><em>O(log n)</em></span> 202 </p> 203 </td> 204</tr> 205<tr> 206<td> 207 </td> 208<td> 209 </td> 210<td> 211 <p> 212 worst case 213 </p> 214 </td> 215<td> 216 <p> 217 <span class="emphasis"><em>O(n)</em></span> 218 </p> 219 </td> 220<td> 221 <p> 222 <span class="emphasis"><em>O(n)</em></span> 223 </p> 224 </td> 225<td> 226 <p> 227 <span class="emphasis"><em>O(n)</em></span> 228 </p> 229 </td> 230<td> 231 <p> 232 <span class="emphasis"><em>O(n)</em></span> 233 </p> 234 </td> 235<td> 236 <p> 237 <span class="emphasis"><em>O(n)</em></span> 238 </p> 239 </td> 240</tr> 241<tr> 242<td> 243 </td> 244<td> 245 </td> 246<td> 247 <p> 248 amortized 249 </p> 250 </td> 251<td> 252 <p> 253 <span class="emphasis"><em>O(log n)</em></span> 254 </p> 255 </td> 256<td> 257 <p> 258 <span class="emphasis"><em>O(log n)</em></span> 259 </p> 260 </td> 261<td> 262 </td> 263<td> 264 </td> 265<td> 266 </td> 267</tr> 268<tr> 269<td> 270 </td> 271<td> 272 <p> 273 <code class="computeroutput"><span class="identifier">interval_sets</span></code> 274 </p> 275 </td> 276<td> 277 </td> 278<td> 279 <p> 280 <span class="emphasis"><em>O(m log(n+m))</em></span> 281 </p> 282 </td> 283<td> 284 <p> 285 <span class="emphasis"><em>O(m log(n+m))</em></span> 286 </p> 287 </td> 288<td> 289 <p> 290 <span class="emphasis"><em>O(m log(n+m))</em></span> 291 </p> 292 </td> 293<td> 294 </td> 295<td> 296 </td> 297</tr> 298<tr> 299<td> 300 </td> 301<td> 302 <p> 303 <code class="computeroutput"><span class="identifier">interval_maps</span></code> 304 </p> 305 </td> 306<td> 307 </td> 308<td> 309 </td> 310<td> 311 </td> 312<td> 313 </td> 314<td> 315 <p> 316 <span class="emphasis"><em>O(m log(n+m))</em></span> 317 </p> 318 </td> 319<td> 320 <p> 321 <span class="emphasis"><em>O(m log(n+m))</em></span> 322 </p> 323 </td> 324</tr> 325</tbody> 326</table></div> 327</div> 328<br class="table-break"><p> 329 Adding an <span class="emphasis"><em>element</em></span> or <span class="emphasis"><em>element value pair</em></span> 330 is always done in <span class="emphasis"><em>logarithmic time</em></span>, where <span class="emphasis"><em>n</em></span> 331 is the number of intervals in the interval container. The same row of complexities 332 applies to the insertion of a <span class="emphasis"><em>segment</em></span> (an interval or 333 an interval value pair) in the <span class="emphasis"><em><span class="bold"><strong>best case</strong></span></em></span>, 334 where the inserted segment does overlap with only a <span class="emphasis"><em><span class="bold"><strong>small</strong></span></em></span> 335 number of intervals in the container. 336 </p> 337<p> 338 In the <span class="emphasis"><em><span class="bold"><strong>worst case</strong></span></em></span>, 339 where the inserted segment overlaps with all intervals in the container, 340 the algorithms iterate over all the overlapped segments. Using inplace manipulations 341 of segments and hinted inserts, it is possible to perform all necessary operations 342 on each iteration step in <span class="emphasis"><em>constant time</em></span>. This results 343 in <span class="emphasis"><em><span class="bold"><strong>linear worst case time</strong></span></em></span> 344 complexity for segment addition for all interval containers. 345 </p> 346<p> 347 After performing a worst case addition for an <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_set</a></code> 348 or a <code class="computeroutput"><a class="link" href="../../boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_sets</a></code> 349 adding an interval that overlaps <span class="emphasis"><em>n</em></span> intervals, we need 350 <span class="emphasis"><em>n</em></span> non overlapping additions of <span class="emphasis"><em>logarithmic 351 time</em></span> before we can launch another <span class="emphasis"><em>O(n)</em></span> worst 352 case addition. So we have only a <span class="emphasis"><em><span class="bold"><strong>logarithmic 353 amortized time</strong></span></em></span> for the addition of an interval or interval 354 value pair. 355 </p> 356<p> 357 For the addition of <span class="emphasis"><em><span class="bold"><strong>interval containers</strong></span></em></span> 358 complexity is <span class="emphasis"><em>O(m log(n+m))</em></span>. So for the <span class="emphasis"><em><span class="bold"><strong>worst case</strong></span></em></span>, where the container sizes 359 <span class="emphasis"><em>n</em></span> and <span class="emphasis"><em>m</em></span> are equal and both containers 360 cover the same ranges, the complexity of container addition is <span class="emphasis"><em><span class="bold"><strong>loglinear</strong></span></em></span>. For other cases, that occur 361 frequently in real world applications performance can be much better. If 362 the added container <code class="computeroutput"><span class="identifier">operand</span></code> 363 is much smaller than <code class="computeroutput"><span class="identifier">object</span></code> 364 and the intervals in <code class="computeroutput"><span class="identifier">operand</span></code> 365 are relatively small, performance can be <span class="emphasis"><em>logarithmic</em></span>. 366 If <span class="emphasis"><em>m</em></span> is small compared with <span class="emphasis"><em>n</em></span> and 367 intervals in <code class="computeroutput"><span class="identifier">operand</span></code> are 368 large, performance tends to be <span class="emphasis"><em>linear</em></span>. 369 </p> 370</div> 371<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 372<td align="left"></td> 373<td align="right"><div class="copyright-footer">Copyright © 2007-2010 Joachim 374 Faulhaber<br>Copyright © 1999-2006 Cortex Software 375 GmbH<p> 376 Distributed under the Boost Software License, Version 1.0. (See accompanying 377 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 378 </p> 379</div></td> 380</tr></table> 381<hr> 382<div class="spirit-nav"> 383<a accesskey="p" href="../implementation.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../implementation.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="inplace_and_infix_operators.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 384</div> 385</body> 386</html> 387
