Concept of Polynomial time


Jun 20, 2024

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






你可能感興趣的文章

JavaScript 閉包(Closure)新手入門解析教學

JavaScript 閉包(Closure)新手入門解析教學

Day 1 - Drum Kit (KeyEvent)

Day 1 - Drum Kit (KeyEvent)

Day5 跟一般的指令可不一樣啊!跟我所認識的指令不同啊!

Day5 跟一般的指令可不一樣啊!跟我所認識的指令不同啊!






留言討論