Seberapa sulit menemukan item dengan kunci?
Itu tergantung pada struktur data mana yang akan digunakan.
Dalam daftar tertaut tunggal, kompleksitas linier.
Dalam larik yang diurutkan atau dalam pohon pencarian biner, kompleksitas log.
Dalam tabel hash, kompleksitasnya konstan. Tapi ini yang terbaik. Dan paling buruk ... cenderung linier ...
-, ?
- . , - , - , , , -.
! , .
, " " OTUS , -.
- . , - . , !
, , - “dog”, -, , , , “”
!
?
, 10.000 -. - 10.000 . “” --, , ? , , “” .
- “(A * k + B) % N”
, A
, “” - . k
- (ulong) , N - .
.
“”, - “”, .
. “” “”, - “”. “ ”, .
“” “”.
, , “” () “” . , .
, 100 10.000 10.
,
- “(A * k + B) % N”
. “”, . “” () “”.
K “” K²
“”. “ ” A
B
K , (, - ). “” -, “”.
!
- :
“”
i
-k: “(A * k + B) % N”
.
:
Ai
,Bi
,K²
.
“” :
“(Ai * k + Bi) % K²
”
“”.
( , ) “” , .
, “” -. , ( ).
, , - N = 10 . 0 10 . , .
: “” N
, “” - 1.9 * N
. : 2.9 * N = (N)
- .
, -, -- () - , .
. 15 Demo Day " " OTUS, .
, :