Độ phức tạp thời gian thực thi trong cấu trúc dữ liệu và giải thuật?
Câu trả lời (1)
-
Có 3 trường hợp thường được sử dụng để so sánh thời gian thực thi của các cấu trúc dữ liệu khác nhau:
- Trường hợp xấu nhất (Worst Case): là tình huống mà một phép tính của cấu trúc dữ liệu nào đó tốn thời gian tối đa (thời gian dài nhất). Ví dụ với ba số 1, 2, 3 thì nếu sắp xếp theo thứ tự giảm dần thì thời gian thực thi sẽ là dài nhất (và đây là trường hợp xấu nhất); còn nếu sắp xếp theo thứ tự tăng dần thì thời gian thực thi sẽ là ngắn nhất (và đây là trường hợp tốt nhất).
- Trường hợp trung bình (Average Case): miêu tả thời gian thực thi trung bình một phép tính của một cấu trúc dữ liệu.
- Trường hợp tốt nhất (Best Case): là tình huống mà thời gian thực thi một phép tính của một cấu trúc dữ liệu là ít nhất. Ví dụ như trên.
bởi Phạm Phú Lộc Nữ
15/11/2021
Like (0) Báo cáo sai phạm
Nếu bạn hỏi, bạn chỉ thu về một câu trả lời.
Nhưng khi bạn suy nghĩ trả lời, bạn sẽ thu về gấp bội!
Lưu ý: Các trường hợp cố tình spam câu trả lời hoặc bị báo xấu trên 5 lần sẽ bị khóa tài khoản
Các câu hỏi mới
-
nhập mảng số nguyên M phần tử (M<>0, M thuộc tập số tự nhiên) đếm số phần tử mà giá trị của nó chia hết cho 3 và 5 trong chương trình.
19/12/2022 | 0 Trả lời
-
trình bày các đặc điểm về khoá chính bảng?
24/12/2022 | 0 Trả lời
-
Viết chương trình kiểu mảng nhập 10 số in ra màn hình các số âm và số âm phải lẻ, đếm xem có bao nhiêu số lẻ
02/02/2023 | 0 Trả lời
-
VIDEOYOMEDIA
Hãy viết chương trình trên Pascal, nhập vào 2 số và tính tổng 2 số đã nhập (ghi kết quả ra màn hình đồng thời ghi 2 số nhập từ bàn phím và tổng của chúng vào tệp “e:\tong2so.doc”).
05/03/2023 | 0 Trả lời
-
Lập chương trình nhập vào 2 chuỗi bất kỳ a, b(với chuỗi b là con của
chuỗi a, tức là trong chuỗi a có 1 phần giống chuỗi b). Sau đó tìm và in ra màn hình vị trí
đầu tiên tìm thấy chuỗi b trong chuỗi a.06/03/2023 | 0 Trả lời
-
Var a : array[0..50] of real
K:= 0
for i := 1 to 50 d
if a[i] > a[k] then k := i
Đoạn chương trình trên thực hiện công việc gì dưới đây?
A. Tìm phần tử nhỏ nhất trong mảng
B. Tìm phần tử lớn nhất trong mản
C. Tìm chỉ số của phần tử lớn nhất trong mả
D. Tìm chỉ số của phần tử nhỏ nhất trong mảng
14/03/2023 | 0 Trả lời
-
Viết chương trình nhập dãy số nguyên gồm 10 số đém có bao nhiêu số chia hết cho 5?
15/03/2023 | 0 Trả lời
-
Viết chương trình nhập vào 1 dãy số nguyên gồm n phân tử tính và viết ra màng hình tổng của số dương trong dãy. (nhập từ bàn phím số phần tử N và các phần tử trong dãy)
16/03/2023 | 0 Trả lời
-
"ABCS"; "?A"; "15.1"; "@THCS"
21.5; 22.6; 30.1; 62.8; 10; 3
"s"; "a"; "?"; "1.5"; "3"
15; 21; 98; 35; 22; 30
20/03/2023 | 0 Trả lời
-
viết chương trình python nhập xâu xoá tất cả các chữ số có trong xâu
23/03/2023 | 0 Trả lời
-
Một tệp văn bản có kích thước 50Kb. Bằng cách nào ta có thể truy cập trực tiếp vào byte thứ 1000 mà không cần đọc qua 999 byte đầu.
24/03/2023 | 0 Trả lời
-
viết chương trình nhập 1 số tự nhiên n từ bàn bàn phím kiểm tra xem n là số nguyên tố hay hợp số. Lưu ý nếu n-0 hoặc n-1 thì không phải là số nguyên tố cũng không phải là hợp số
30/04/2023 | 0 Trả lời
-
a, Viết các khai báo biến cần thiết.
b, Viết các thủ tục gắn tên tệp và mở tệp phù hợp.
c, Viết câu lệnh để đọc các số nguyên a từ tệp ‘DULIEU.INP’ rồi ghi các số không chia hết cho 7 và tổng của các số đó vào tệp ‘KCHIA7.TXT’.
07/05/2023 | 0 Trả lời
-
Nhập vào dãy số nguyên có 200 số. Hãy hiển thị ra màn hình những số chẵn?
08/05/2023 | 0 Trả lời
-
Viết chương trình C++ để nhập một số nguyên x và n. Tính giá trị của
t=x - 1/3!x3 + 1/5!x5 - 1/7!x7 + 1/9!x9+…+1/n!(xn).
14/07/2023 | 0 Trả lời

