Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = 2n(n - 2) + 4.
b) T(n) = n3 + 5n - 3.
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
HQ
Hà Quang Minh
Giáo viên
22 tháng 9 2023
a) \(\lim \frac{{5n + 1}}{{2n}} = \lim \frac{{5 + \frac{1}{n}}}{2} = \frac{{5 + 0}}{2} = \frac{5}{2}\)
b) \(\lim \frac{{6{n^2} + 8n + 1}}{{5{n^2} + 3}} = \lim \frac{{6 + \frac{8}{n} + \frac{1}{{{n^2}}}}}{{5 + \frac{3}{{{n^2}}}}} = \frac{{6 + 0 + 0}}{{5 + 0}} = \frac{6}{5}\)
c) \(\lim \frac{{\sqrt {{n^2} + 5n + 3} }}{{6n + 2}} = \lim \frac{{\sqrt {1 + \frac{5}{n} + \frac{3}{{{n^2}}}} }}{{6 + \frac{2}{n}}} = \frac{{\sqrt {1 + 0 + 0} }}{{6 + 0}} = \frac{1}{6}\)
d) \(\lim \left( {2 - \frac{1}{{{3^n}}}} \right) = \lim 2 - \lim {\left( {\frac{1}{3}} \right)^n} = 2 - 0 = 0\)
e) \(\lim \frac{{{3^n} + {2^n}}}{{{{4.3}^n}}} = \lim \frac{{1 + {{\left( {\frac{2}{3}} \right)}^n}}}{4} = \frac{{1 + 0}}{4} = \frac{1}{4}\)
g) \(\lim \frac{{2 + \frac{1}{n}}}{{{3^n}}}\)
Ta có \(\lim \left( {2 + \frac{1}{n}} \right) = \lim 2 + \lim \frac{1}{n} = 2 + 0 = 2 > 0;\lim {3^n} = + \infty \Rightarrow \lim \frac{{2 + \frac{1}{n}}}{{{3^n}}} = 0\)
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
Công việc của hàm là thực hiện sắp xếp.
Độ phức tạp của thuật toán là O(n2)
AH
Akai Haruma
Giáo viên
29 tháng 1 2023
a.
\(A=\lim\frac{\sqrt[3]{n^6-7n^3-5n+8}}{n+12}=\lim \frac{\sqrt[3]{\frac{n^6-7n^3-5n+8}{n^3}}}{\frac{n+12}{n}}=\lim \frac{\sqrt[3]{n^3-7-\frac{5}{n^2}+\frac{8}{n^3}}}{1+\frac{12}{n}}\)
Ta thấy:
\(\lim\sqrt[3]{n^3-7-\frac{5}{n^2}+\frac{8}{n^3}}=\infty \)
\(\lim (1+\frac{12}{n})=1\)
Suy ra $A=\infty$
AH
Akai Haruma
Giáo viên
29 tháng 1 2023
b.
\(B=\lim\frac{1}{\sqrt{3n+2}-\sqrt{2n+1}}=\lim \frac{1}{\frac{3n+2-(2n+1)}{\sqrt{3n+2}+\sqrt{2n+1}}}=\lim \frac{\sqrt{3n+2}+\sqrt{2n+1}}{n+1}\)
\(=\lim \frac{\sqrt{\frac{3n+2}{n}}+\sqrt{\frac{2n+1}{n}}}{\frac{n+1}{\sqrt{n}}}=\lim \frac{\sqrt{3+\frac{2}{n}}+\sqrt{2+\frac{1}{n}}}{\sqrt{n}+\frac{1}{\sqrt{n}}}\)
Ta thấy:
\(\lim( \sqrt{3+\frac{2}{n}}+\sqrt{2+\frac{1}{n}})=\sqrt{3}+\sqrt{2}>0\)
\(\lim (\sqrt{n}+\frac{1}{\sqrt{n}})=\infty\)
$\Rightarrow B=\infty$
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)
NV
Nguyễn Việt Lâm
Giáo viên
7 tháng 2 2021
\(a=\lim\dfrac{5n\left(n+\sqrt{n^2-n-1}\right)}{n+1}=\lim\dfrac{5\left(n+\sqrt{n^2-n-1}\right)}{1+\dfrac{1}{n}}=\dfrac{+\infty}{1}=+\infty\)
\(b=\lim\dfrac{\sqrt{\dfrac{1}{n}+\sqrt{\dfrac{1}{n^3}+\dfrac{1}{n^4}}}}{1-\dfrac{1}{\sqrt{n}}}=\dfrac{0}{1}=0\)
\(c=\lim\dfrac{\sqrt{2n^2-1+\dfrac{7}{n^2}}}{3+\dfrac{5}{n}}=\dfrac{+\infty}{3}=+\infty\)
\(d=\lim\dfrac{\sqrt{3+\dfrac{2}{n}}-1}{3-\dfrac{2}{n}}=\dfrac{\sqrt{3}-1}{3}\)
a) T(n) = 2n(n - 2) + 4 = 2n2 - 4n + 4 = O(n2)
b) T(n) = n3 + 5n – 3 = O(n3)