25:
477:
Decomposition is a term used in computer science to break static data structures into smaller units of unequal size. The basic principle is the idea that any decimal number can be translated into a representation in any other base. For more details about the topic see
1111:
1005:
662:-th bit equal to 0, the corresponding set does not contain any elements. Each of the subset has the same property as the original static data structure. Operations performed on the new dynamic data structure may involve traversing
145:
one. Although static data structures may provide very good functionality and fast queries, their utility is limited because of their inability to grow/shrink quickly, thus making them inapplicable for the solution of
1231:
467:
701:
744:
1152:
874:
834:
794:
1011:
903:
550:
251:
915:
580:
322:
660:
640:
620:
600:
507:
342:
295:
271:
216:
196:
176:
752:
proved several equations for time complexity of operations on the data structures dynamized according to this idea. Some of these equalities are listed.
1161:
347:
116:
479:
50:
97:
46:
69:
482:. For simplicity, binary system will be used in this article but any other base (as well as other possibilities such as
147:
76:
150:, where the input data changes. Dynamization techniques provide uniform ways of creating dynamic data structures.
1259:
746:
factor as opposed to the static data structure operations but will allow insert/delete operation to be added.
35:
83:
665:
706:
142:
54:
39:
138:
1106:{\displaystyle {\overline {I}}=O\left(\left(P_{S}\left(n\right)/n\right)\cdot \log \left(n\right)\right).}
1119:
841:
801:
761:
65:
881:
515:
1000:{\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\cdot \log \left(n\right)\right)}
483:
221:
130:
558:
300:
90:
645:
625:
605:
585:
492:
327:
280:
256:
201:
181:
161:
1243:
1253:
749:
24:
1155:
876:
is the time to query the dynamic data structure formed by decomposition
1226:{\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\right)}
16:
Process of transforming a static data structure into a dynamic one
462:{\displaystyle P(M,S)=P(M,S_{0})+P(M,S_{1})+\dots +P(M,S_{n})}
18:
703:
sets formed by decomposition. As a result, this will add
1164:
1122:
1014:
918:
884:
844:
804:
764:
709:
668:
648:
628:
608:
588:
561:
518:
495:
350:
330:
303:
283:
259:
224:
204:
184:
164:
509:elements is broken down into subsets of sizes with
1225:
1146:
1105:
999:
897:
868:
828:
788:
738:
695:
654:
634:
614:
594:
574:
544:
501:
461:
336:
316:
289:
265:
245:
210:
190:
170:
836:is the time to query the static data structure
796:is the time to build the static data structure
1246:3, . An EATCS Series, vol. 3, Springer, 1984.
8:
53:. Unsourced material may be challenged and
1201:
1169:
1163:
1127:
1121:
1062:
1045:
1015:
1013:
955:
923:
917:
885:
883:
849:
843:
809:
803:
769:
763:
708:
673:
667:
647:
627:
607:
587:
566:
560:
536:
523:
517:
494:
450:
416:
388:
349:
329:
308:
302:
282:
258:
223:
203:
183:
163:
117:Learn how and when to remove this message
696:{\displaystyle \log _{2}\left(n\right)}
739:{\displaystyle O(\log \left(n\right))}
489:If using the binary system, a set of
7:
51:adding citations to reliable sources
1147:{\displaystyle Q_{S}\left(n\right)}
869:{\displaystyle Q_{D}\left(n\right)}
829:{\displaystyle Q_{S}\left(n\right)}
789:{\displaystyle P_{S}\left(n\right)}
14:
137:is the process of transforming a
480:Decomposition (computer science)
344:of result unification such that
23:
905:is the amortized insertion time
898:{\displaystyle {\overline {I}}}
297:can be decomposed into subsets
178:of searching for the predicate
1244:Data structures and algorithms
733:
713:
622:in binary. This means that if
456:
437:
422:
403:
394:
375:
366:
354:
324:and there exists an operation
240:
228:
1:
1020:
890:
154:Decomposable search problems
545:{\displaystyle 2^{i}*n_{i}}
1276:
486:) can also be utilized.
1227:
1148:
1107:
1001:
899:
870:
830:
790:
740:
697:
656:
636:
616:
596:
576:
546:
503:
463:
338:
318:
291:
267:
247:
246:{\displaystyle P(M,S)}
212:
192:
172:
1228:
1149:
1108:
1002:
900:
871:
831:
791:
741:
698:
657:
637:
617:
597:
577:
575:{\displaystyle n_{i}}
547:
504:
464:
339:
319:
317:{\displaystyle S_{i}}
292:
268:
248:
213:
193:
173:
139:static data structure
1162:
1120:
1012:
916:
882:
842:
802:
762:
707:
666:
646:
626:
606:
586:
559:
516:
493:
348:
328:
301:
281:
257:
222:
202:
182:
162:
47:improve this article
1223:
1144:
1103:
997:
895:
866:
826:
786:
736:
693:
652:
632:
612:
592:
572:
542:
499:
459:
334:
314:
287:
263:
243:
208:
188:
168:
158:We define problem
1023:
893:
655:{\displaystyle i}
635:{\displaystyle n}
615:{\displaystyle n}
595:{\displaystyle i}
502:{\displaystyle n}
484:Fibonacci numbers
337:{\displaystyle +}
290:{\displaystyle S}
266:{\displaystyle P}
211:{\displaystyle S}
198:match in the set
191:{\displaystyle M}
171:{\displaystyle P}
127:
126:
119:
101:
1267:
1232:
1230:
1229:
1224:
1222:
1218:
1217:
1206:
1205:
1185:
1174:
1173:
1153:
1151:
1150:
1145:
1143:
1132:
1131:
1112:
1110:
1109:
1104:
1099:
1095:
1094:
1074:
1070:
1066:
1061:
1050:
1049:
1024:
1016:
1006:
1004:
1003:
998:
996:
992:
991:
971:
960:
959:
939:
928:
927:
904:
902:
901:
896:
894:
886:
875:
873:
872:
867:
865:
854:
853:
835:
833:
832:
827:
825:
814:
813:
795:
793:
792:
787:
785:
774:
773:
745:
743:
742:
737:
732:
702:
700:
699:
694:
692:
678:
677:
661:
659:
658:
653:
641:
639:
638:
633:
621:
619:
618:
613:
601:
599:
598:
593:
581:
579:
578:
573:
571:
570:
551:
549:
548:
543:
541:
540:
528:
527:
508:
506:
505:
500:
468:
466:
465:
460:
455:
454:
421:
420:
393:
392:
343:
341:
340:
335:
323:
321:
320:
315:
313:
312:
296:
294:
293:
288:
272:
270:
269:
264:
252:
250:
249:
244:
217:
215:
214:
209:
197:
195:
194:
189:
177:
175:
174:
169:
148:dynamic problems
131:computer science
122:
115:
111:
108:
102:
100:
59:
27:
19:
1275:
1274:
1270:
1269:
1268:
1266:
1265:
1264:
1260:Data structures
1250:
1249:
1242:Kurt Mehlhorn,
1239:
1237:Further reading
1207:
1197:
1196:
1192:
1175:
1165:
1160:
1159:
1133:
1123:
1118:
1117:
1084:
1051:
1041:
1040:
1036:
1035:
1031:
1010:
1009:
981:
961:
951:
950:
946:
929:
919:
914:
913:
880:
879:
855:
845:
840:
839:
815:
805:
800:
799:
775:
765:
760:
759:
722:
705:
704:
682:
669:
664:
663:
644:
643:
624:
623:
604:
603:
584:
583:
562:
557:
556:
555:elements where
532:
519:
514:
513:
491:
490:
475:
446:
412:
384:
346:
345:
326:
325:
304:
299:
298:
279:
278:
255:
254:
220:
219:
200:
199:
180:
179:
160:
159:
156:
123:
112:
106:
103:
60:
58:
44:
28:
17:
12:
11:
5:
1273:
1271:
1263:
1262:
1252:
1251:
1248:
1247:
1238:
1235:
1221:
1216:
1213:
1210:
1204:
1200:
1195:
1191:
1188:
1184:
1181:
1178:
1172:
1168:
1142:
1139:
1136:
1130:
1126:
1114:
1113:
1102:
1098:
1093:
1090:
1087:
1083:
1080:
1077:
1073:
1069:
1065:
1060:
1057:
1054:
1048:
1044:
1039:
1034:
1030:
1027:
1022:
1019:
1007:
995:
990:
987:
984:
980:
977:
974:
970:
967:
964:
958:
954:
949:
945:
942:
938:
935:
932:
926:
922:
907:
906:
892:
889:
877:
864:
861:
858:
852:
848:
837:
824:
821:
818:
812:
808:
797:
784:
781:
778:
772:
768:
735:
731:
728:
725:
721:
718:
715:
712:
691:
688:
685:
681:
676:
672:
651:
631:
611:
591:
569:
565:
553:
552:
539:
535:
531:
526:
522:
498:
474:
471:
458:
453:
449:
445:
442:
439:
436:
433:
430:
427:
424:
419:
415:
411:
408:
405:
402:
399:
396:
391:
387:
383:
380:
377:
374:
371:
368:
365:
362:
359:
356:
353:
333:
311:
307:
286:
262:
242:
239:
236:
233:
230:
227:
207:
187:
167:
155:
152:
125:
124:
66:"Dynamization"
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1272:
1261:
1258:
1257:
1255:
1245:
1241:
1240:
1236:
1234:
1219:
1214:
1211:
1208:
1202:
1198:
1193:
1189:
1186:
1182:
1179:
1176:
1170:
1166:
1157:
1140:
1137:
1134:
1128:
1124:
1100:
1096:
1091:
1088:
1085:
1081:
1078:
1075:
1071:
1067:
1063:
1058:
1055:
1052:
1046:
1042:
1037:
1032:
1028:
1025:
1017:
1008:
993:
988:
985:
982:
978:
975:
972:
968:
965:
962:
956:
952:
947:
943:
940:
936:
933:
930:
924:
920:
912:
911:
910:
887:
878:
862:
859:
856:
850:
846:
838:
822:
819:
816:
810:
806:
798:
782:
779:
776:
770:
766:
758:
757:
756:
753:
751:
750:Kurt Mehlhorn
747:
729:
726:
723:
719:
716:
710:
689:
686:
683:
679:
674:
670:
649:
629:
609:
589:
567:
563:
537:
533:
529:
524:
520:
512:
511:
510:
496:
487:
485:
481:
473:Decomposition
472:
470:
451:
447:
443:
440:
434:
431:
428:
425:
417:
413:
409:
406:
400:
397:
389:
385:
381:
378:
372:
369:
363:
360:
357:
351:
331:
309:
305:
284:
276:
260:
237:
234:
231:
225:
205:
185:
165:
153:
151:
149:
144:
140:
136:
132:
121:
118:
110:
107:February 2023
99:
96:
92:
89:
85:
82:
78:
75:
71:
68: –
67:
63:
62:Find sources:
56:
52:
48:
42:
41:
37:
32:This article
30:
26:
21:
20:
1154:is at least
1115:
908:
754:
748:
554:
488:
476:
275:decomposable
274:
157:
135:dynamization
134:
128:
113:
104:
94:
87:
80:
73:
61:
45:Please help
33:
602:-th bit of
277:if the set
1156:polynomial
253:. Problem
77:newspapers
1082:
1076:⋅
1021:¯
979:
973:⋅
891:¯
720:
680:
530:∗
429:⋯
34:does not
1254:Category
582:is the
1158:, then
143:dynamic
141:into a
91:scholar
55:removed
40:sources
93:
86:
79:
72:
64:
909:then
98:JSTOR
84:books
755:If
642:has
70:news
38:any
36:cite
1116:If
1079:log
976:log
717:log
671:log
273:is
218:as
129:In
49:by
1256::
1233:.
469:.
133:,
1220:)
1215:)
1212:n
1209:(
1203:S
1199:Q
1194:(
1190:O
1187:=
1183:)
1180:n
1177:(
1171:D
1167:Q
1141:)
1138:n
1135:(
1129:S
1125:Q
1101:.
1097:)
1092:)
1089:n
1086:(
1072:)
1068:n
1064:/
1059:)
1056:n
1053:(
1047:S
1043:P
1038:(
1033:(
1029:O
1026:=
1018:I
994:)
989:)
986:n
983:(
969:)
966:n
963:(
957:S
953:Q
948:(
944:O
941:=
937:)
934:n
931:(
925:D
921:Q
888:I
863:)
860:n
857:(
851:D
847:Q
823:)
820:n
817:(
811:S
807:Q
783:)
780:n
777:(
771:S
767:P
734:)
730:)
727:n
724:(
714:(
711:O
690:)
687:n
684:(
675:2
650:i
630:n
610:n
590:i
568:i
564:n
538:i
534:n
525:i
521:2
497:n
457:)
452:n
448:S
444:,
441:M
438:(
435:P
432:+
426:+
423:)
418:1
414:S
410:,
407:M
404:(
401:P
398:+
395:)
390:0
386:S
382:,
379:M
376:(
373:P
370:=
367:)
364:S
361:,
358:M
355:(
352:P
332:+
310:i
306:S
285:S
261:P
241:)
238:S
235:,
232:M
229:(
226:P
206:S
186:M
166:P
120:)
114:(
109:)
105:(
95:·
88:·
81:·
74:·
57:.
43:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
