多項式時間








多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。


多項式時間のアルゴリズムとは、解くべき問題の入力サイズn{displaystyle n}nに対して、処理時間の上界としてn{displaystyle n}nの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。


たとえばバブルソートの処理時間は要素数n{displaystyle n}nに対して要素の比較・交換を行う回数は高々 12n(n−1){displaystyle {frac {1}{2}}n(n-1)}{frac {1}{2}}n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO(n2){displaystyle O({n^{2}})}{displaystyle O({n^{2}})}と表される。 またクイックソートの期待計算量のオーダーはO(nlog⁡n){displaystyle O(nlog n)}O(nlog n)、最悪計算量のオーダーはO(n2){displaystyle O({n^{2}})}{displaystyle O({n^{2}})}である。




目次






  • 1 定義


    • 1.1 多項式時間アルゴリズム


    • 1.2 多項式時間アルゴリズムが存在する問題とクラスP




  • 2 関連項目





定義


多項式時間アルゴリズムと多項式時間アルゴリズムが存在する問題クラスについて、簡単に記す。



多項式時間アルゴリズム


Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは多項式時間アルゴリズムであるという


ある多項式l(k)があって、任意のkと任意のkビットのデータxに対し、Aにxを入力した時にAが停止するまでのステップ数はl(k)以下である。

なお「多項式時間アルゴリズム」と言った場合、決定的アルゴリズムのみを多項式時間アルゴリズムとして認める場合と、確率的アルゴリズムをも許す場合とがある。



多項式時間アルゴリズムが存在する問題とクラスP


決定的な多項式時間アルゴリズム（上で定義した）で解ける判定問題の集合をクラスPと呼ぶ（判定問題以外の問題はクラスPに含まれないことに注意）。



関連項目



  • 計算量理論

  • 定数時間

  • 指数関数時間

  • 多項式時間変換

  • 凖指数関数時間

  • 時間計算量




Popular posts from this blog

android studio warns about leanback feature tag usage required on manifest while using Unity exported app?

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 This is a simple project showing cubes on Unity, exported to android project and imported on Android studio. On maifest file it showed following warning: Expecting <uses-feature android:name="android.software.leanback" android:required="false" /> tag I have no information about it. And also on default emptyview android project does not use/mention this feature. I know it is required by TV's and such but why its not added by default? Why is this? And Should I concern about it? android unity3d
Read more

SQL update select statement

Image
0 I'm trying to update an entry in my database (postgresql). I'm having a problem with updating the query: INSERT INTO prices (price, product_id) SELECT product_price, commn_id FROM products_temp as prod WHERE NOT EXISTS (SELECT * FROM prices od WHERE prod.commn_id = od.product_id) OR prod.product_price != ( SELECT price FROM prices as p WHERE p.product_id = prod.commn_id order by p.end desc LIMIT 1 ) Query works fine when i delete: OR prod.product_price != ( SELECT price FROM prices as p WHERE p.product_id = prod.commn_id order by p.end desc LIMIT 1 ) So it seems to me that it's looping through this operation. My question is, how can I fix it? sql postgresql
Read more

'app-layout' is not a known element: how to share Component with different Modules

Image
0 My application was working fine until I decided to go with lazy loading: So, my shared component looks like this: import { Component, Renderer2 } from '@angular/core'; export interface FormModel { captcha?: string; } @Component({ selector: 'app-layout', templateUrl: './app-layout.component.html', styleUrls: ['./app-layout.css'] }) export class FullLayoutComponent { } app-layout.component.ts I am using this component in my Another component say school-home.component.html like this: <app-layout> </app-layout> and it was working fine until I created a Module school-home.module.ts like this: import { NgModule } from '@angular/core'; import { CommonModule } from '@angular/common'; import { SchoolhomeRoutingModule
Read more