Concept of Polynomial time


Introduction

In computer science, the efficiency of an algorithm is determined by how its running time or space requirements increase with the size of the input. "Polynomial time" is a key concept in this evaluation, describing a specific class of computational efficiency. Understanding polynomial time is essential for analyzing and comparing algorithms, especially when working with large datasets.

Defining Polynomial Time

An algorithm runs in polynomial time if its running time can be represented as a polynomial function of the input size. In other words, an algorithm operates in polynomial time if there is a constant k where the running time T(n) for an input of size n is O(n^k). This Big-O notation sets an upper limit on time complexity, disregarding constant factors and lower-order terms.

Non-Polynomial Time Algorithms

On the other hand, some problems necessitate algorithms that do not run in polynomial time. These algorithms often exhibit exponential time complexities like O(2^n), making them impractical for large inputs. Examples include specific combinatorial optimization problems and NP-complete problems, which are thought to lack polynomial time solutions.

List of Complexity Classes

  • O(1) - Constant time
  • O(log(n)) - Logarithmic time
  • O((log(n))^c) - Polylogarithmic time
  • O(n) - Linear time
  • O(n log(n)) - Linearithmic time
  • O(n^2) - Quadratic time
  • O(n^c) - Polynomial time
  • O(c^n) - Exponential time
  • O(n!) - Factorial time
    (n = size of input, c = some constant)

Big-O Complexity Chart

Reference

#time complexity






你可能感興趣的文章

C# 用ini檔讀寫暫存資料

C# 用ini檔讀寫暫存資料

CSS保健室|font-display

CSS保健室|font-display

我要成為前端工程師的學習筆記:HTML & CSS 篇 - 文字排版、線條 Day4

我要成為前端工程師的學習筆記:HTML & CSS 篇 - 文字排版、線條 Day4






留言討論