Hãy viết một đoạn chương trình có độ phức tạp thời gian là tuyến tính.
K
Khách
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Những câu hỏi liên quan
QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023
*Chương trình 1:
from collections import Counter
import time
n = 1000
c = 0
# Ghi lại thời điểm bắt đầu
start_time = time.time()
for k in range(n):
c = c + 1
# Ghi lại thời điểm kết thúc
end_time = time.time()
# Tính thời gian hoàn thành
elapsed_time = end_time - start_time
# Sử dụng hàm Counter để đếm số lần lặp
counter = Counter(range(n))
# In số lần lặp
print("Số lần lặp: {}".format(counter))
# In thời gian thực thi
print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))
*Chương trình 2:
import time
n = 1000
c = 0
# Ghi lại thời điểm bắt đầu
start_time = time.perf_counter()
for k in range(n):
for j in range(n):
c = c + 1
# Ghi lại thời điểm kết thúc
end_time = time.perf_counter()
# Tính thời gian hoàn thành
elapsed_time = end_time - start_time
# In số lần lặp
print("Số lần lặp: {}".format(c))
# In thời gian thực thi
print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))
→Sự khác biệt độ phức tạp thời gian của 2 chương trình trên:
Độ phức tạp thời gian của chương trình 1 là O(1), còn độ phức tạp thời gian của chương trình 2 là O(n2).
QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023
Đánh giá được mức đơn giản của thuật toán, từ đó tìm ra được cách giải nhanh nhất.
QT
Quoc Tran Anh Le
Giáo viên
23 tháng 8 2023
Chương trình trên tính số lần lặp cần thiết để i lớn hơn n bằng cách nhân i với 2 trong mỗi lần lặp, sau đó tăng biến sum lên 1. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng while và các phép toán trong vòng lặp.
Vòng while: Vòng lặp này chạy cho đến khi i >= n, và giá trị ban đầu của i là 1. Trong mỗi lần lặp, i được nhân với 2, vậy số lần lặp là log2(n) (vì sau mỗi lần nhân i với 2, giá trị của i sẽ gấp đôi). Ví dụ, nếu n = 1000 thì số lần lặp là log2(1000) ≈ 10.
Các phép toán trong vòng lặp:
Phép gán i = i * 2: Đây là phép nhân, có độ phức tạp là O(1).
Phép gán sum = sum + 1: Đây là phép gán giá trị vào biến sum, có độ phức tạp là O(1).
Vậy tổng độ phức tạp thời gian của chương trình là O(log n), hay O(log2(1000)) ≈ O(10)
TA
18 tháng 7 2023
THAM KHẢO!
Chương trình trên tính tổng các giá trị i*(i+1) trong khoảng từ 0 đến n-1 và lưu kết quả vào biến s. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng for và các phép toán trong vòng lặp.
Vòng for: Vòng lặp này chạy từ 0 đến n-1, với n là 1.000. Vậy số lần lặp là n, hay 1.000 lần.
Các phép toán trong vòng lặp:
Phép gán s = s + i*(i+1): Đây là phép gán giá trị vào biến s, có độ phức tạp là O(1).
Phép toán i*(i+1): Đây là phép nhân và cộng, có độ phức tạp là O(1).
Vậy tổng độ phức tạp thời gian của chương trình là O(n), hay O(1.000)
LD
25 tháng 4 2024
tính E(300)=300/log2(300), E(90000)=90000/log2(90000)
Vì độ hiệu quả tỉ lệ thuận với thời gian thực hiện
nên ta có tỉ số 0,02/E(300)=x/E(90000) (x là giá trị cần tìm).
Từ đó tính được x=3
QT
Quoc Tran Anh Le
Giáo viên
9 tháng 11 2023
1. Tính số lần lặp của vòng lặp bên trong của thuật toán sắp xếp chèn tuyến tính.
2. Tính số lần lặp của vòng lặp ngoài của thuật toán sắp xếp chèn tuyến tính.
3. Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính:
Vòng lặp for bên ngoài kiểm soát việc thực hiện đúng n-1 bước.
Vòng lặp while lồng bên trong thực hiện đồng thời cùng lúc hai việc a) và b) theo cách dịch chuyển dần từng bước sang trái, từ vị trí i tới vị trí k+1
27 tháng 10 2021
1:
#include <bits/stdc++.h>
using namespace std;
long long n,i,s;
int main()
{
cin>>n;
s=0;
for (i=1; i<=n; i++)
s=s+i*i;
cout<<s;
return 0;
}
A
27 tháng 1 2022
Mượn luôn câu chủ đề nhé !!
Bài Làm
Trong cơn đại dịch Covid-19 diễn biến phức tạp, có rất nhiều người có những biểu hiện xa lánh, thậm chí là kỳ thị những người từ vùng dịch về hoặc người có tiếp xúc với người bệnh,thậm chí đôi khi họ còn miệt thị những người vùng dịch .....Vì sao vậy ? Họ sợ rằng những người đó sẽ lây bệnh cho mình , họ sợ rằng thực tế là ta đang sống chung với dịch bệnh . Trong suốt năm 2019 đến giờ dịch bệnh đã gieo rắc xuống toàn thế giới nhiều điều mà chúng ta không thể lường trước được .Tính đến đầu tháng 6/2020, hơn 7 triệu người được xác nhận mắc Covid-19, hơn 406.000 người tử vong . Covid bắt nguồn từ Vũ Hán, Trung Quốc . Tuy chúng ta thực hiện vô cùng tốt trong công tác phòng chống dịch, mọi thứ đều được thực hiện theo quy định, kiểm soát tình hình dịch bệnh trong cả nước được nâng lên mức cao nhất.. Nhưng dường như những cố gắng đó là không đủ .Để phòng chống Covid thì đầu tiên, ta cần phải tự ý thức được trách nhiệm góp phần chung tay vào phòng chống dịch bệnh. Khi thấy bản thân có những dấu hiệu như sốt, ho, khó thở,… hay có tiếp xúc gần với các ca lây nhiễm được công bố thì phải lập tức thông báo tới cơ sở y tế để kiểm tra, và tiến hành cách ly an toàn. Mỗi người đều phải trang bị đầy đủ khẩu trang, nước rửa tay khô mỗi khi ra đường, rửa thường xuyên với dung dịch khử trùng mỗi khi tiếp xúc mới bề mặt cứng ở ngoài.
nonononononononononon
xin lỗi