Schlange als dynamisches Feld - Aufwand

[oSnake]

Hallo Leute,

ich soll den Aufwand bei einer Schlange die als dynamisches Feld implementiert wird errechnen.

Die Schlange kann am Anfang 10 Elemente enthalten. Bei Erreichen der Kapazität wird das Feld jeweils um 10 Elemente vergrößert.

Wie hoch ist der amotisierte Aufwand von Einfügungen?


Ich will keine "Lösung" sondern ein Hinweis würde hier schon reichen denke ich.

 

[stg]

Was ist denn ein "dynamisches Feld"?

 

[oSnake]

Eine dynamische Datenstruktur mit einer flexiblen Menge als Speicherplatz.

- Wenn das Feld voll ist, wird ein doppelt so grosses Feld erzeugt
- Elemente werden rüberkopiert

 

[mrBrown]

Also im wesentlichen nur ein einfaches Array?

 

[oSnake]

Im Prinzip - ja.

 

[Xyz1]

Wenn nicht voll: 1
Wenn voll: n+9
amortisiert: 1/10*(n+9)
um einfacher zu rechnen: (n+10)/10=n/10+1
nun wissen wir: n/10 in O(n)

 

[Xyz1]

Es kommt drauf an, wie genau ihr das machen sollt. Also: (1/10)*(n+10)+1+(9/10)*1

Aber n/10 würd mir schon genügen.

 

[Joose]

- Wenn das Feld voll ist, wird ein doppelt so grosses Feld erzeugt

Wird das Feld verdoppelt oder um 10 vergrößert?

 

[Meniskusschaden]

Aber n/10 würd mir schon genügen.

Mir nicht. Welcher Aufwand ist damit denn überhaupt gemeint? Der Gesamtaufwand für das Einfügen aller n Elemente? Da müßte doch etwas größeres heraus kommen. Oder der durchschnittliche Aufwand für das Einfügen eines Elements? Da scheint mir n/10 etwas hoch gegriffen (selbst in der Variante mit der Erweiterung um zehn - also ohne Verdoppelung).

 

[Xyz1]

Mir nicht. Welcher Aufwand ist damit denn überhaupt gemeint?

Das steht weiter oben:
"Wie hoch ist der amotisierte Aufwand von Einfügungen?"

Der Aufwand, um ein Elem einzufügen.

An der Stelle ist auch die Aufgabenstellung eindeutig - und ich denke mal, dass er/TE sich mit "verdoppeln" einfach verschrieben hat.

 

[Xyz1]

Der Aufwand, um 200 Elemente einzufügen, wäre z. B.:
https://www.wolframalpha.com/input/?i=sum+n/10,+n=1+to+200
(2010)
oder:
https://www.wolframalpha.com/input/?i=sum+(1/10)*(n+10)+1+(9/10)*1,+n=1+to+200
(2590)
etwas genauer.

Der Aufwand, um ein Elem einzufügen: O(n)
Der Aufwand, um n Elem einzufügen: O(n^2)

 

[Meniskusschaden]

Ich kann deine Formeln nicht nachvollziehen. Nehmen wir als Beispiele n=20 und n=29. Bei n=10 wird das Array das erste Mal vergrößert (auf 20), bei n=20 das zweite Mal (auf 30). Bei n=20 gibt es also wieder 10 freie Plätze, bei n=29 nur noch einen. Laut deiner Formel müsste folgendes heraus kommen:

n=20:
(1/10)*(n+10)+1+(9/10)*1
=(1/10)*(20+10)+1+(9/10)*1
=(0,1)*(30)+1+(0,9)
=3+1,9
=4,9

n=29:
(1/10)*(n+10)+1+(9/10)*1
=(1/10)*(29+10)+1+(9/10)*1
=(0,1)*(39)+1+(0,9)
=3,9+1,9
=5,8

(Etwas seltsam, weil 29 Elemente pro Element nicht teurer sondern günstiger als 20 sein müssten, aber darum geht es mir gerade nicht).
Wenn man einfach abzählt, hat man bei n=20 offensichtlich 20 Einfüge-Operationen und 30 Kopier-Operationen. Bei n=29 sind es 29 Einfüge- und 30 Kopier-Operationen. Also folgende Ergebnisse:

(20+30)/20 = 2,5 (statt 4,9)
(29+30)/29 = 2,03 (statt 5,8)

Die Abschätzung n/10 passt bei diesen Beispielen aber noch ganz gut. Allerdings haben wir beispielsweise bei n=99, also Arraygröße 100 mit einem freien Platz, schon 99 Einfüge- und 450 Kopier-Operationen, also (99+450)/99 = 5,5. Bei n/10 würden wir 9,9 erhalten und bei deiner Formel (1/10)*(99+10)+1+(9/10)*1 = 12,8

 

[mrBrown]

Ich bin ja für einen anderen Ansatz: Das Array vergrößern ist im wesentlichen nur einmal das Array kopieren: Einen Speicherbereich duplizieren=O(1), ein Element danach einfügen auch, also landet man bei O(1) SCNR

 

[Meniskusschaden]

Einen Speicherbereich duplizieren=O(1), ein Element danach einfügen auch, also landet man bei O(1) SCNR

Ich glaube, @DerWissende hat schon die Obergrenze O(n) festgelegt. Aber da die Werte nicht so richtig passen, müsste man meines Erachtens noch zeigen, dass der Aufwand nicht niedriger ist (was er wohl tatsächlich nicht ist).

 

[Xyz1]

Ich kann deine Formeln nicht nachvollziehen.

Rechne es nach, um exakte Ergebnisse zu erhalten:

    static int array[] = new int[0];
    static int i = 0;
    static int n = 0;

    static void reset() {
        array = new int[0];
        int i = 0;
        int n = 0;
    }

    static void add(int e) {
        if (i == array.length) {
            int array2[] = new int[array.length + 10];
            for (int j = 0; j < array.length; j++) {
                array2[j] = array[j];
                n++;
            }
            array = array2;
        }
        array[i++] = e;
        n++;
    }

    public static void main(String[] args) {
        for (int j = 1; j < 201; j++) {
            add(j);
            System.out.println(j + "\t" + n + "\t" + sum1(j) + "\t" + sum2(j));
        }
    }

    static float sum1(int e) {
        float sum = 0;
        while (e > 0) {
            sum += e-- / 10.0;
        }
        return sum;
    }

    static float sum2(int e) {
        float sum = 0;
        while (e > 0) {
            sum += (1 / 10.0) * (e-- + 10) + (9 / 10.0) * 1;
        }
        return sum;
    }

1	1	0.1	2.0
2	2	0.3	4.1
3	3	0.6	6.3
4	4	1.0	8.6
5	5	1.5	11.0
6	6	2.1	13.500001
7	7	2.8	16.1
8	8	3.6	18.8
9	9	4.4999995	21.6
10	10	5.5	24.500002
11	21	6.6	27.5
12	22	7.7999997	30.6
13	23	9.1	33.800003
14	24	10.500001	37.1
15	25	12.0	40.5
16	26	13.6	44.0
17	27	15.300001	47.6
18	28	17.1	51.3
19	29	19.0	55.1
20	30	21.0	59.0
21	51	23.1	62.999996
22	52	25.300001	67.1
23	53	27.6	71.299995
24	54	30.0	75.6
25	55	32.5	80.0
26	56	35.1	84.5
27	57	37.8	89.1
28	58	40.6	93.8
29	59	43.5	98.6
30	60	46.499996	103.5
31	91	49.6	108.5
32	92	52.800003	113.6
33	93	56.1	118.799995
34	94	59.5	124.1
35	95	63.0	129.5
36	96	66.6	135.0
37	97	70.3	140.6
38	98	74.1	146.3
39	99	78.0	152.1
40	100	81.99999	158.0
41	141	86.1	164.0
42	142	90.299995	170.1
43	143	94.6	176.3
44	144	99.0	182.6
45	145	103.5	189.0
46	146	108.1	195.50002
47	147	112.8	202.1
48	148	117.6	208.79999
49	149	122.5	215.6
50	150	127.5	222.5
51	201	132.6	229.5
52	202	137.8	236.6
53	203	143.1	243.8
54	204	148.5	251.1
55	205	154.0	258.5
56	206	159.6	266.0
57	207	165.3	273.6
58	208	171.1	281.3
59	209	177.0	289.1
60	210	183.0	297.0
61	271	189.1	305.0
62	272	195.3	313.1
63	273	201.6	321.3
64	274	208.0	329.6
65	275	214.50002	338.0
66	276	221.1	346.5
67	277	227.79999	355.1
68	278	234.6	363.8
69	279	241.5	372.6
70	280	248.5	381.5
71	351	255.6	390.5
72	352	262.80002	399.6
73	353	270.1	408.80002
74	354	277.5	418.1
75	355	285.0	427.5
76	356	292.6	437.0
77	357	300.3	446.6
78	358	308.1	456.3
79	359	316.0	466.1
80	360	324.0	476.0
81	441	332.1	486.0
82	442	340.3	496.1
83	443	348.6	506.30002
84	444	357.0	516.6
85	445	365.5	527.0
86	446	374.1	537.5
87	447	382.8	548.1
88	448	391.6	558.8
89	449	400.5	569.6
90	450	409.5	580.49994
91	541	418.6	591.5
92	542	427.80002	602.6
93	543	437.1	613.8
94	544	446.5	625.1
95	545	456.0	636.5
96	546	465.6	648.0
97	547	475.3	659.6
98	548	485.1	671.30005
99	549	495.0	683.1
100	550	505.0	695.0
101	651	515.1	707.0
102	652	525.3	719.1
103	653	535.6	731.3
104	654	546.0	743.6
105	655	556.5	756.0
106	656	567.1	768.5
107	657	577.8	781.1
108	658	588.6	793.8
109	659	599.49994	806.6
110	660	610.5	819.5
111	771	621.6	832.49994
112	772	632.8	845.6
113	773	644.1	858.8
114	774	655.5	872.1
115	775	667.0	885.5
116	776	678.6	899.0
117	777	690.30005	912.6
118	778	702.1	926.3
119	779	714.0	940.1
120	780	726.0	954.0
121	901	738.1	967.99994
122	902	750.3	982.1
123	903	762.6	996.30005
124	904	775.0	1010.6
125	905	787.5	1025.0
126	906	800.1	1039.5
127	907	812.8	1054.1
128	908	825.6	1068.8
129	909	838.5	1083.6
130	910	851.49994	1098.5
131	1041	864.6	1113.5
132	1042	877.8	1128.6
133	1043	891.1	1143.7999
134	1044	904.5	1159.1
135	1045	918.0	1174.4999
136	1046	931.6	1190.0
137	1047	945.3	1205.6
138	1048	959.1	1221.3
139	1049	973.0	1237.1
140	1050	986.99994	1253.0
141	1191	1001.1	1269.0
142	1192	1015.30005	1285.1
143	1193	1029.6	1301.2999
144	1194	1044.0	1317.6
145	1195	1058.5	1334.0
146	1196	1073.1	1350.5
147	1197	1087.8	1367.1
148	1198	1102.6	1383.7999
149	1199	1117.5	1400.6
150	1200	1132.5	1417.5
151	1351	1147.6	1434.4999
152	1352	1162.7999	1451.6
153	1353	1178.1	1468.8
154	1354	1193.4999	1486.1
155	1355	1209.0	1503.5
156	1356	1224.6	1521.0
157	1357	1240.3	1538.6
158	1358	1256.1	1556.3
159	1359	1272.0	1574.1
160	1360	1288.0	1592.0
161	1521	1304.1	1610.0
162	1522	1320.2999	1628.1
163	1523	1336.6	1646.2999
164	1524	1353.0	1664.6
165	1525	1369.5	1683.0
166	1526	1386.1	1701.5
167	1527	1402.7999	1720.1
168	1528	1419.6	1738.8
169	1529	1436.5	1757.6
170	1530	1453.4999	1776.5
171	1701	1470.6	1795.5
172	1702	1487.8	1814.6
173	1703	1505.1	1833.7999
174	1704	1522.5	1853.1
175	1705	1540.0	1872.5
176	1706	1557.6	1891.9999
177	1707	1575.3	1911.6
178	1708	1593.1	1931.3
179	1709	1611.0	1951.1
180	1710	1629.0	1970.9999
181	1891	1647.1	1991.0
182	1892	1665.2999	2011.1
183	1893	1683.6	2031.3
184	1894	1702.0	2051.6
185	1895	1720.5	2072.0
186	1896	1739.1	2092.5
187	1897	1757.8	2113.1
188	1898	1776.6	2133.8
189	1899	1795.5	2154.6
190	1900	1814.5	2175.5
191	2091	1833.6	2196.5
192	2092	1852.7999	2217.6
193	2093	1872.1	2238.7998
194	2094	1891.5	2260.1
195	2095	1910.9999	2281.5
196	2096	1930.6	2303.0
197	2097	1950.3	2324.6
198	2098	1970.1	2346.2998
199	2099	1989.9999	2368.1
200	2100	2010.0	2390.0

1. Nummer, 2. wirkliche Kosten, 3. Kostenschätzung fahrlässig, 4. Kostenschätzung nicht ganz so fahrlässig.

Folgerung: Die Wahrheit liegt irgendwo dazwischen.

 

[Meniskusschaden]

Ja, das scheint gut zu passen. Ich habe deine Formel aus Post #7 als den durchschnittlichen Aufwand pro Element bei n Elementen aufgefasst. Es ist aber wohl der Aufwand des n-ten Elements. Also muß man noch aufsummieren und durch n dividieren, um auf die Zahl zu kommen, die ich erwartet hatte.

 

[Xyz1]

Ich habe deine Formel aus Post #7 als den durchschnittlichen Aufwand pro Element bei n Elementen aufgefasst.

Mit der Info kann ich nicht so viel anfangen.
Wenn n Elemente in der "Schlange" sind, möchte ich wissen, wie hoch der Aufwand ist, um ein (n+1). Element einzufügen.
So stehts auch in allen Java Docs.
"Wie hoch ist der amotisierte Aufwand von Einfügungen?"
amortisiert !== durchschnittlich

BTW.: Gibt es eine JVM möglichkeit, alle Zuweisungen während einer Programmlaufzeit zu zählen? Ist mir zB nicht bekannt. Aber wäre mega praktisch...

Aufwand, um n Elemente einzufügen: SumI von 1 bis n (I/10)
Durchschnittlicher Aufwand, um n Element einzufügen: SumI von 1 bis n (I/10) / n
!!!!

Sorry, hübsch ist das nicht.