polynomial time
Nghĩa tiếng Việt
Definition & Meaning
English Definition
In computational complexity theory, polynomial time is the amount of time taken by an algorithm to solve a problem, where the time is expressed as a polynomial function of the input size.
Vietnamese Meaning
Trong lý thuyết độ phức tạp tính toán, thời gian đa thức là lượng thời gian mà một thuật toán cần để giải quyết một vấn đề, trong đó thời gian được biểu diễn dưới dạng một hàm đa thức của kích thước đầu vào.
Media Context
Interactive Examples (Tap video to Pause/Play).
Examples
-
"Many fundamental problems in computer science can be solved in polynomial time."
"Nhiều bài toán cơ bản trong khoa học máy tính có thể được giải quyết trong thời gian đa thức."
-
"Algorithms that run in polynomial time are considered efficient."
"Các thuật toán chạy trong thời gian đa thức được coi là hiệu quả."
-
"Determining whether a graph is connected can be done in polynomial time."
"Việc xác định xem một đồ thị có liên thông hay không có thể được thực hiện trong thời gian đa thức."
Word Family (Họ từ)
| POS | Word | Meaning |
|---|---|---|
| Noun | polynomial | Đa thức (một biểu thức toán học gồm tổng của các đơn thức với các biến số và hệ số) |
| Adjective | polynomial | Thuộc về đa thức; liên quan đến đa thức (ví dụ: a polynomial function – một hàm đa thức) |
| Adverb | polynomially | Theo cách đa thức; với độ phức tạp đa thức (ví dụ: a problem solvable polynomially – một bài toán có thể giải theo kiểu đa thức) |
Antonyms
Related Words
Subject Area
Etymology (Nguồn gốc)
Usage Note
Cụm từ này mô tả một lớp các thuật toán được coi là 'hiệu quả' hơn so với các thuật toán có độ phức tạp thời gian tăng theo cấp số mũ (ví dụ: thời gian mũ). Nó là một khái niệm quan trọng trong việc phân loại các vấn đề tính toán thành các lớp có thể giải quyết được một cách thực tế.
Prepositions
‘In’ được dùng trong ngữ cảnh ‘in polynomial time’ để chỉ rằng thuật toán có thể giải quyết vấn đề trong thời gian đa thức. ‘For’ ít phổ biến hơn nhưng có thể được dùng để chỉ khoảng thời gian đa thức dành cho việc thực hiện một tác vụ cụ thể, ví dụ: 'the algorithm runs for polynomial time'.
Collocations (Từ đi kèm)
-
run in run in polynomial time (chạy trong thời gian đa thức (ám chỉ thuật toán hoàn thành trong khoảng thời gian hiệu quả))
-
solve in solve in polynomial time (giải quyết trong thời gian đa thức (ám chỉ một bài toán có thể tìm ra lời giải hiệu quả))
-
require require polynomial time (yêu cầu thời gian đa thức (thời gian cần thiết để thực hiện một tác vụ, thường mang nghĩa là hiệu quả))
-
in in polynomial time (trong thời gian đa thức (diễn tả khả năng giải quyết một vấn đề một cách hiệu quả))
-
within within polynomial time (trong phạm vi thời gian đa thức (tương tự 'in polynomial time', nhấn mạnh giới hạn thời gian hiệu quả))
-
efficient efficient polynomial time (thời gian đa thức hiệu quả (nhấn mạnh tính hiệu quả của một thuật toán có độ phức tạp đa thức))
-
quasi- quasi-polynomial time (thời gian gần đa thức (một loại độ phức tạp tính toán nằm giữa đa thức và siêu đa thức))
Idioms
-
solvable in polynomial time
có thể giải quyết được trong thời gian đa thức (một thuật ngữ kỹ thuật chỉ rằng một bài toán có lời giải hiệu quả, thời gian chạy không tăng quá nhanh khi kích thước đầu vào lớn)
"Many fundamental problems in computer science are solvable in polynomial time."
(Nhiều vấn đề cơ bản trong khoa học máy tính có thể giải quyết được trong thời gian đa thức.)
-
polynomial time algorithm
thuật toán thời gian đa thức (một thuật toán có độ phức tạp thời gian tăng theo một hàm đa thức của kích thước đầu vào, được coi là hiệu quả)
"The QuickSort algorithm is considered a polynomial time algorithm on average."
(Thuật toán QuickSort được coi là một thuật toán thời gian đa thức ở trường hợp trung bình.)
-
polynomial time complexity
độ phức tạp thời gian đa thức (một đặc điểm của thuật toán cho biết thời gian chạy của nó được giới hạn bởi một hàm đa thức của kích thước đầu vào)
"Researchers are trying to find a method with polynomial time complexity for this challenging problem."
(Các nhà nghiên cứu đang cố gắng tìm ra một phương pháp có độ phức tạp thời gian đa thức cho bài toán đầy thách thức này.)
Interactive Flashcard
Click the card to flip and test your memory.
polynomial time
Danh từ (cụm danh từ)Trong lý thuyết độ phức tạp tính toán, thời gian đa thức là lượng thời gian mà một thuật toán cần để giải quyết một vấn đề, trong đó thời gian được biểu diễn dưới dạng một hàm đa thức của kích thước đầu vào.
"Many fundamental problems in computer science can be solved in polynomial time."
Grammar Rules
Rule: Future Continuous Tense (Thì Tương lai Tiếp diễn)
| Loại câu | Ví dụ Tiếng Anh | Bản dịch Tiếng Việt |
|---|---|---|
| Khẳng định | The computer will be processing the data in polynomial time. |
Máy tính sẽ đang xử lý dữ liệu trong thời gian đa thức. |
| Phủ định | The algorithm won't be running in polynomial time, it will take much longer. |
Thuật toán sẽ không chạy trong thời gian đa thức, nó sẽ mất nhiều thời gian hơn. |
| Nghi vấn | Will the program be executing in polynomial time or will it timeout? |
Chương trình sẽ thực thi trong thời gian đa thức hay nó sẽ hết thời gian? |
Cultural Context
Khám phá các khía cạnh văn hóa và xã hội thú vị xoay quanh từ "polynomial time".