eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Privatundervisning
Kontakt
eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Privatundervisning
Kontakt
eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Privatundervisning
Kontakt
eksamenssett
.no
Tren målrettet
Ungdomsskole/VGS
Høyskole
Ressurser
Privatundervisning
Kontakt
Hjem
Høyskole
NTNU
TDT4120
Quiz
Dagens quiz – Dynamisk programmering
Dagens quiz – Dynamisk programmering
Spørsmål 1 av 10
0%
Hva er rekurrensen for Edit Distance (Levenshtein)?
Dynamisk programmering
A
Bruk én rad istedenfor full tabell:
O
(
W
)
O(W)
O
(
W
)
plass i stedet for
O
(
n
W
)
O(nW)
O
(
nW
)
B
Antall mulige binære trær / matrise-parantesplasseringer for
n
n
n
ledd
C
F
(
n
)
=
F
(
n
−
1
)
+
F
(
n
−
2
)
F(n) = F(n-1) + F(n-2)
F
(
n
)
=
F
(
n
−
1
)
+
F
(
n
−
2
)
med
O
(
n
)
O(n)
O
(
n
)
tid og
O
(
1
)
O(1)
O
(
1
)
plass (bottom-up)
D
d
[
i
,
j
]
=
min
(
d
[
i
−
1
,
j
]
+
1
,
d
[
i
,
j
−
1
]
+
1
,
d
[
i
−
1
,
j
−
1
]
+
[
x
i
≠
y
j
]
)
d[i,j] = \min(d[i-1,j]+1, d[i,j-1]+1, d[i-1,j-1] + [x_i \ne y_j])
d
[
i
,
j
]
=
min
(
d
[
i
−
1
,
j
]
+
1
,
d
[
i
,
j
−
1
]
+
1
,
d
[
i
−
1
,
j
−
1
]
+
[
x
i
=
y
j
])
Vis hint
Rapporter feil