thắc mắc Hash map tìm kiếm nhanh vậy sao còn phải học Linear search và Binary search

Nipin said:

cãi có đưa ra dẫn chứng là tốt rồi. hơn khối người.

cơ mà thực tế thì còn nhiều cái phải cân nhắc, kiểu như hàm hash key của hashmap nó cũng không trivial, rồi thì lúc resize lại phải tính lại hashes...

làm gì thì cũng tuỳ bài toán thôi.. ví dụ như bài đầu dữ liệu tĩnh thì tôi dùng for loop rồi bật -O3 là nó fold thành constants, sao phải xoắn :v

Click to expand...

-O3 là gì thím

Tập Làm Coder said:

Suốt ngày post mấy cái topic vậy hèn chi 30 tuổi vẫn đ có việc làm


https://cs.stackexchange.com/questions/23068/how-do-o-and-Ω-relate-to-worst-and-best-case

Click to expand...

Rồi quăng cái link rồi có đọc không vậy, chứ tui chưa thấy tui sai chỗ nào hết á

theo mình thì khi code sẽ tính tới trường hợp xấu nhất, chứ ai đi chăm chăm vào best case làm gì nhỉ ? đến lúc xảy ra lỗi thì lại bảo với customer là "ơ tao tưởng.." à?

lyokha113 said:

Rồi quăng cái link rồi có đọc không vậy, chứ tui chưa thấy tui sai chỗ nào hết á
View attachment 461338

Click to expand...

Tìm hiẻu thêm đi fen nếu chỗ ý đọc chưa hiểu, nhưng nó viết rõ lắm rùi đâys

Tập Làm Coder said:

Tìm hiẻu thêm đi fen nếu chỗ ý đọc chưa hiểu, nhưng nó viết rõ lắm rùi đâys

Click to expand...

Bạn bảo sai thì bạn chỉ hộ ra là sai chỗ nào chứ toàn nói vô căn cứ vậy , cảm thấy khả năng đọc hiểu thật sự có vấn đề.
Bạn muốn google quăng link ? Thì đây

Ref


Ref

Ngay cả chính link bạn quăng bừa lên mà bạn còn không thèm đọc




p/s: có vấn đề gì về thần kinh cảm xúc ko mà cứ spam reaction vậy bạn

lyokha113 said:

Bạn bảo sai thì bạn chỉ hộ ra là sai chỗ nào chứ toàn nói vô căn cứ vậy , cảm thấy khả năng đọc hiểu thật sự có vấn đề.
Bạn muốn google quăng link ? Thì đây
View attachment 461409
Ref

View attachment 461414
Ref

Ngay cả chính link bạn quăng bừa lên mà bạn còn không thèm đọc

View attachment 461420


p/s: có vấn đề gì về thần kinh cảm xúc ko mà cứ spam reaction vậy bạn

Click to expand...

Trong mấy trường hợp này bác nên bỏ qua đừng để tâm.Trong thời gian bác giải thích thì bác có thể kiếm ra nhiều giá trị hơn rồi.
Dù sao cũng cảm ơn bác cho em đọc nhiều kiến thức mới

lyokha113 said:

Bạn bảo sai thì bạn chỉ hộ ra là sai chỗ nào chứ toàn nói vô căn cứ vậy , cảm thấy khả năng đọc hiểu thật sự có vấn đề.
Bạn muốn google quăng link ? Thì đây
View attachment 461409
Ref

View attachment 461414
Ref

Ngay cả chính link bạn quăng bừa lên mà bạn còn không thèm đọc

View attachment 461420


p/s: có vấn đề gì về thần kinh cảm xúc ko mà cứ spam reaction vậy bạn

Click to expand...

Upper với best case là 2 từ giống nhau à, bạn đọc ông kia nói từ nothing to do, chú ý vào đoạn ý, tui đang làm công nhân tay đầy dầu mỡ với cả có bọn giám sát nên ko type kỹ giải thích cho fen đc

hieuicttn said:

theo mình thì khi code sẽ tính tới trường hợp xấu nhất, chứ ai đi chăm chăm vào best case làm gì nhỉ ? đến lúc xảy ra lỗi thì lại bảo với customer là "ơ tao tưởng.." à?

Click to expand...

Code sẽ tính trường hợp trung bình, thi thoảng vào best, thi thoảng vào worst.

ông có thấy ai cố tình viết cho nó hết vào worst case ko?

như cái ông tối qua tui cãi nhau, cứ bảo tui hash search O(1) là sai

trong khi tui đang nói trường hợp phổ biến

Như cái linear search hay binary người ta có chăm chăm đc nó luôn vào best case( phần tử tìm đc luôn là vị trí index 0 hay index mid) đâu. Hay là với worst là luôn luôn ở index vị trí "end" đâu

giả dụ mà tui đang dùng hash mà lúc đéo cũng worst thì tui dùng chi fen?

mấy thín trên kia có đưa các use case cho hash thì tui ưng, ông kia nhảy vào bảo ko phải O(1) tui chả vào cãi à

KiKan11 said:

Trong mấy trường hợp này bác nên bỏ qua đừng để tâm.Trong thời gian bác giải thích thì bác có thể kiếm ra nhiều giá trị hơn rồi.
Dù sao cũng cảm ơn bác cho em đọc nhiều kiến thức mới

Click to expand...

Thật ra 3 cái notations đó và các cái "worst-case", "best-case" trong các trường hợp nói về DSA là "khác nhau".
Nói đúng ra là sử dụng Big O để miêu tả worst-case cho các case khác nhau.
Ví dụ Quicksort đi, ta sẽ nói time complexity trong trường hợp pivot đẹp là O(nlogn), và khi phân bổ pivot không hợp lý thì là O(n^2), aka đó là worst-case trong từng trường hợp này, và case sau "worst" hơn case trước.
Do đó người ta thuờng chỉ xài Big O thay vì theta và Omega để nói về complexity.

Đồng nghĩa với việc bạn kia quote 1 câu bảo sai nhưng không có context, giải thích gì thì chỉ là nói càn

Tập Làm Coder said:

Code sẽ tính trường hợp trung bình, thi thoảng vào best, thi thoảng vào worst.

ông có thấy ai cố tình viết cho nó hết vào worst case ko?

như cái ông tối qua tui cãi nhau, cứ bảo tui háh search O(1 )

Click to expand...

nhầm nhé. bao giờ test thì tester cũng coi trọng worst case hơn. vì wc chạy được thì bc cũng ok. chứ nếu cứ xử lý trung bình thì lúc wc xảy ra lỗi thì ai chịu trách nhiệm? hay lại bảo đấy là tính năng. có những khi QA nó test những trường hợp mà 99% ng dùng chả thằng nào rảnh để làm thế mà vẫn phải fix đấy

ôi. lậm vào xử lý tầng trên quá r. đang bàn về thuật toán. sorry anh em. mình chỉ hóng tiếp thôi chứ k mon men comment nữa

lyokha113 said:

Thật ra 3 cái notations đó và các cái "worst-case", "best-case" trong các trường hợp nói về DSA là "khác nhau".
Nói đúng ra là sử dụng Big O để miêu tả worst-case cho các case khác nhau.
Ví dụ Quicksort đi, ta sẽ nói time complexity trong trường hợp pivot đẹp là O(nlogn), và khi phân bổ pivot không hợp lý thì là O(n^2), aka đó là worst-case trong từng trường hợp này, và case sau "worst" hơn case trước.
Do đó người ta thuờng chỉ xài Big O thay vì theta và Omega để nói về complexity.

Đồng nghĩa với việc bạn kia quote 1 câu bảo sai nhưng không có context, giải thích gì thì chỉ là nói càn

Click to expand...

Context gì, đưa link cho thì đọc lại ko hiểu, nhận ngu thì có sao đâu fen

Tập Làm Coder said:

Context gì, đưa link cho thì đọc lại ko hiểu, nhận ngu thì có sao đâu fen

Click to expand...

Big oh (O) – Worst case
Big Omega (Ω) – Best case
Big Theta (Θ) – Average case
Sai chỗ nào vậy bạn, thong thả chứng minh, thong thả type, không cần phải vội, không ai hối bạn đâu.
Nhớ là giải thích nhé, chứ đừng có quăng cái link vô thưởng vô phạt mà "khôn" như bạn cũng không hiểu chính bạn post gì

lyokha113 said:

Big oh (O) – Worst case
Big Omega (Ω) – Best case
Big Theta (Θ) – Average case
Sai chỗ nào vậy bạn, thong thả chứng minh, thong thả type, không cần phải vội, không ai hối bạn đâu.
Nhớ là giải thích nhé, chứ đừng có quăng cái link vô thưởng vô phạt mà "khôn" như bạn cũng không hiểu chính bạn post gì

Click to expand...

Không phải trên kia vừa nhận ra khác nhau rùi à, đưa cái context big Omega là best case cho tui xem nào. Đã khác nhau thì ng ta bảo nó ko liên quan, lại lôi cái context vào, giờ anh em vào đọc lại hiểu sai theo, như ông kia kìa

Tập Làm Coder said:

Không phải trên kia vừa nhận ra khác nhau rùi à, đưa cái context big Omega là best case cho tui xem nào. Đã khác nhau thì ng ta bảo nó ko liên quan, lại lôi cái context vào, giờ anh em vào đọc lại hiểu sai theo, như ông kia kìa

Click to expand...

Có vấn đề thị giác à mà không thấy 2 bức hình to vậy còn bảo đưa ? Kém khả năng đọc hiểu à mà không google ra được ? Hay do học hành không tới nơi tới chốn ? Càng nói càng cùn

Big oh (O) – Worst case
Big Omega (Ω) – Best case
Big Theta (Θ) – Average case
Bạn bảo sai thì chứng minh, còn không thì đừng có cùn nữa, kém thật sự

lyokha113 said:

Có vấn đề thị giác à mà không thấy 2 bức hình to vậy còn bảo đưa ? Kém khả năng đọc hiểu à mà không google ra được ? Hay do học hành không tới nơi tới chốn ? Càng nói càng cùn

Big oh (O) – Worst case
Big Omega (Ω) – Best case
Big Theta (Θ) – Average case
Bạn bảo sai thì chứng minh, còn không thì đừng có cùn nữa, kém thật sự

Click to expand...

Ông lại page 2, có ông kia rep omega() là best case. Sau đó tui bảo là sai rồi. Và ông kêu " sai chỗ nào" và nói viết 3 dòng kia là ông đồng tình với ông ý chứ gì?

và tôi đã đưa ra cái link là 2 cái không liên quan rồi, còn bắt chứng minh cái gì nhỉ?

2 cái hình ông gửi ở chỗ nào nó khẳng định onega() là best case, ông bôi đen chỗ ý hộ tôi

P/s: như ông kia KiKan11 bảo, mấy trường hợp như ông chắc tui nên bỏ qua. Đây là cmt cuối cùng

Tập Làm Coder said:

Ông lại page 2, có ông kia rep omega() là best case. Sau đó tui bảo là sai rồi. Và ông kêu " sai chỗ nào" và nói viết 3 dòng kia là ông đồng tình với ông ý chứ gì?

và tôi đã đưa ra cái link là 2 cái không liên quan rồi, còn bắt chứng minh cái gì nhỉ?

2 cái hình ông gửi ở chỗ nào nó khẳng định onega() là best case, ông bôi đen chỗ ý hộ tôi

P/s: như ông kia KiKan11 bảo, mấy trường hợp như ông chắc tui nên bỏ qua. Đây là cmt cuối cùng

Click to expand...

SAI chỗ nào ??

Càng nói càng cùn thì có gì để nói nữa mà không bỏ qua, tư duy kém, đọc hiểu kém cả 3 page, kiến thức 3 cái notations này thì không có mà hở tí là cạnh khóe thế này ra vẻ thế nọ

Hashmap là datastructure để lưu và truy suất data

Linear vs binary search là thuật toán để tìm kiếm, ko chỉ áp dụng trên array mà còn có nhiều ứng dụng khác, tuy nhiên khi đi học thì đc làm quen vs ví dụ là tìm trên array nên nhiều người nghĩ là chỉ có thể dùng vs array (học vẹt). Ví dụ: tìm căn của 1 số x có thể dùng binary search, tìm giá trị cực đại/tiểu cho hàm bậc 2 cũng có thể dùng binary search, tìm giá trị min/max trong hashmap v.v... thậm chí là tìm commit nào có bug cũng có thể semi automate bằng binary search

Code tính average case, tất nhiên là có worst case nhưng xác suất thấp. Ko cứ dùng merge sort lúc nào chả nlogn, việc gì phải quick sort khi worst case là n^2.

katoshi said:

Post đó đugns mà thím.
Khi các key trùng hash. Thì dùng 1 cái balanced tree để lưu trữ cấc key trùng hash , để đạt tới 0(logN)
Đây là lý do mình kêu tùy implement , ko hẳn là O(N)đâuá thím.

Click to expand...

à thks thím. không đọc kĩ tự gạch