, . 1951 . , . , . , , 1956 . ( 1), . .
1970 , , , , , , .
. , , , . , , (1970 ) . , , , O(n3). , (1974 ). , , , (1972 ). , , , . .
, ∆ -. ∆ - ∆. , , ∆ (). ∆= 1 , , 1 . ∆ 2 , log2U ∆ -. 1973 , , , , . , O(nm) , , , O(logU).
|
|
1
.
O(n2mU) | ||
O(nmU) | ||
; | O(nm2) | |
O(n2m) | ||
; | O(m2 log U) | |
; | O(mn log U) | |
O(n3) | ||
O(n2√m) | ||
O(n(n+m) log 2(n+m)) | ||
O(nm log 2n) | ||
O(nm log n) | ||
O(nm log (n2/m)) | ||
O(nm+n2 log U) | ||
. | O(nm log (n/m*√l og U)) | |
E(nm+n2 log U)3 | ||
O(n3/ log n) | ||
O(nm+n8/3 log n | ||
. | O(nm+n2+e) | |
O(nm( log m/nn+ log 2+en)) | ||
O (nm log m/(n log n) n) | ||
O(min(n 2/3, m 1/2) m log(n2/m) log U) |
. , U ( ), - . n - , m - .
1970 , , , . , . , , O(I log 2I), I=n+m.
1974 O(n3), XX . O(n2m), 4 O(n3, . . 1986 , O(nm log(n2/m)) , -. 1983 , O(nm log n).
1987 , O(nm+n2 log U). , , . ( , ) O(nm log (n/m*√ log U)).
, , O(min(n2/3, m1/2)m) O(m3/2) . , . , , . O(m√n), .
|
|
. , O(nm), , . 1997 , -,
, , O(nm) .
, . -. , . , , .
. , , 1978 , , . , 1983 O(m log n). - , , , . . , .