프로그래밍 방식으로 획득 Big-O 의 효율성 코드

Question

내가 궁금해 있는지 어떤 자동 방법의 결정(적어도 대략)Big-O 시간 복잡도 주어진 기능이 있나요?

면 저는 그래프 O(n)함수는 대O(n lg n)함수를 생각 나는 것을 시각적으로 확인하는 것은 어떤;나는 생각하고 있을 휴리스틱 솔루션이 이를 가능하게 하는 것이 자동으로 수행됩니다.

어떤 아이디어가?

편집: 나는 행복을 찾는 반 자동화 솔루션,무이 있는지 여부의 어떤 방법을 피하는 일을 완벽하게 설명서 분석합니다.

Answer 1

당신이 요구하는 것은 중단 문제의 연장 인 것 같습니다. 나는 이론적으로도 그런 것이 가능하다고 믿지 않는다.

"이 코드 라인이 실행될 것인가?"라는 질문에 대답합니다. 일반적인 경우에는 불가능하지 않으면 매우 어려울 것입니다.

추가로 편집 : 일반적인 사례는 다루기 어려운데 부분적 해결책을 보려면 여기를 참조하십시오. http://research.microsoft.com/apps/pubs/default.aspx?id=104919

또한 일부는 수작업으로 분석을 수행하는 것이 유일한 선택이지만, 그것이 실제로 그것을 보는 올바른 방법이라고 생각하지 않습니다. 인간이 시스템/기계에 추가 된 경우에도 다루기 어려운 문제는 여전히 다루기 힘들다. 추가 반성 후, 나는 99% 솔루션이 가능할 수 있으며 인간보다 더 잘 작동 할 수도 있다고 생각합니다.

Answer 2

다양한 크기의 데이터 세트를 통해 알고리즘을 실행할 수 있으며 곡선 피팅을 사용하여 근사치를 만들 수 있습니다. (대부분의 경우 생성 된 곡선을 보면 충분하지만 통계 패키지에는 곡선 피팅이 있습니다).

일부 알고리즘은 작은 데이터 세트가있는 한 가지 모양을 나타내지 만 다른 알고리즘은 크고 큰 것입니다 ... 큰 정의는 약간 성가신 상태입니다. 이는 성능 곡선이 우수한 알고리즘이 실제 세계 오버 헤드를 가질 수있어 (작은 데이터 세트의 경우) 이론적으로 더 나은 알고리즘뿐만 아니라 작동하지 않습니다.

한 코드 검사 기술, 아무도 존재하지 않습니다. 그러나 코드가 다양한 길이로 실행되도록 계측하고 간단한 파일을 출력하는 것이 쉽습니다. 적절한 테스트 데이터를 생성하는 것이 더 복잡 할 수 있습니다 (일부 알고리즘은 부분적으로 주문한 데이터에서 더 잘 작동/악화되므로 데이터를 생성하려고합니다. 정상적인 사용 사례를 나타냅니다).

"큰 것"의 정의와 성능이 데이터에 달려 있다는 사실에 대한 문제로 인해 정적 분석이 종종 오해의 소지가 있음을 알게됩니다. 성능을 최적화하고 두 알고리즘을 선택할 때 실제 세계 "고무는 도로에 닿습니다"테스트는 내가 신뢰하는 유일한 최종 중재자입니다.

Answer 3

짧은 대답은 그것은 불가능하기 때문에 상수관.

예를 들어,내가 쓸 수 있는 기능에서 실행됩 O((n^3/k) + n^2).단순 O(n^3)n 기가이, n^3 기를 지배하게 될 것이다 함수,관계없이 일정 k.

그러나,경우 k 은 매우 큰 위의 예에서 기능 함수가 실행되는 것으로 나타나기에 거의 정확하게 n^2 을 때까지 어떤 크로스오버 지점에서 n^3 기를 지배하기 시작.기 때문에 일정 k 이 알 수 없는 어떤 프로파일링 도구는 것은 불가능할 것이 얼마나 큰 데이터 집합을 테스트하는 대상 기능을 가진.는 경우 k 될 수 있는 임의 크기할 수 없는 기술 테스트 데이터를 결정하는 대형 오행 실행 시간입니다.

Answer 4

왜 당신 이이 일을 할 수 있기를 원한다는 것이 궁금합니다. 누군가가 다음과 같이 말할 때 : "이 알고리즘의 런타임 복잡성을 확인하고 싶다"고 그들은 그들이 무엇을 요구하는지 묻지 않습니다. 당신이 가장 많이 묻는 것은 가능성있는 데이터에 대한 이러한 알고리즘의 현실적인 성능은 무엇입니까? 함수의 Big-O를 계산하는 것은 합리적인 유용성이지만, 계측 및 테스트를 능가하는 것은 아무것도 비롯해서 알고리즘의 "실시간 성능"을 변경할 수있는 많은 측면이 있습니다.

예를 들어, 다음 알고리즘은 동일한 정확한 Big-O (엉뚱한 의사 코드)를 갖습니다.

예 A :

huge_two_dimensional_array foo
for i = 0, i < foo[i].length, i++
  for j = 0; j < foo[j].length, j++
    do_something_with foo[i][j]

예 B :

huge_two_dimensional_array foo
for j = 0, j < foo[j].length, j++
  for i = 0; i < foo[i].length, i++
    do_something_with foo[i][j]

다시 말하지만, 정확히 같은 big-o ... 그러나 그들 중 하나는 행 의식을 사용하고 그중 하나는 열 안수를 사용합니다. 참조 및 캐시 일관성의 위치로 인해 두 가지가있을 수 있습니다. 완전히 실제 런타임, 특히 배열 FOO의 실제 크기에 따라 다릅니다. 이것은 동시성이 내장 된 소프트웨어 조각의 일부인 경우 알고리즘이 어떻게 작동하는지에 대한 실제 성능 특성을 터치하기 시작하지 않습니다.

부정적인 Nelly가 아니지만 Big-O는 좁은 범위를 가진 도구입니다. 알고리즘 분석 내부에 깊이 있거나 노력하고있는 경우에는 큰 도움이됩니다. 입증하다 알고리즘에 관한 것, 그러나 상용 소프트웨어 개발을 수행하는 경우 증거는 푸딩에 있으며, 실제 성능을 갖기 위해 지능적인 결정을 내릴 것입니다.

건배!

Answer 5

나는 스톱워치에 의해 복잡성을 "측정"할 수 있다고 주장하려는 많은 시도를보고 놀랐다. 몇몇 사람들은 정답을 주었지만 여전히 필수 지점을 집으로 몰아 넣을 여지가 있다고 생각합니다.

1. 알고리즘 복잡성은 "프로그래밍"질문이 아닙니다. "컴퓨터 과학"질문입니다. 질문에 답하려면 수학자의 관점에서 코드를 분석해야하므로 Big-O 복잡성을 계산하는 것은 실제로 수학적 증거의 한 형태입니다. 기본 컴퓨터 작업, 대수, 아마도 미적분학 (한계) 및 논리에 대한 매우 강력한 이해가 필요합니다. 해당 프로세스를 위해 양의 "테스트"를 대체 할 수 없습니다.

2. 정지 문제가 적용되므로 알고리즘의 복잡성은 기계에 의해 근본적으로 결정되지 않습니다.

3. 자동화 된 도구의 한계가 적용됩니다, 따라서 도움을 줄 프로그램을 작성할 수는 있지만 계산기가 물리 숙제에 도움이되거나 리팩토링 브라우저가 코드 기반을 재구성하는 데 도움이되는만큼 도움이 될 수 있습니다.

4. 그러한 도구를 작성하는 것을 진지하게 고려하는 사람에게는 다음 연습을 제안합니다. 주제 알고리즘과 같이 좋아하는 종류와 같은 합리적으로 간단한 알고리즘을 선택하십시오. 알고리즘 복잡성과 궁극적으로 "Big-O"를 계산하는 프로세스를 통해 확실한 참조 (책, 웹 기반 자습서)를 얻으십시오. 주제 알고리즘으로 프로세스를 거칠 때 단계와 결과를 문서화하십시오. Best-Case, 최악의 경우 및 평균 사례와 같은 여러 시나리오에 대한 단계를 수행하고 진행 상황을 문서화하십시오. 완료되면 문서를 검토하고 프로그램 (도구)을 작성하는 데 필요한 것이 무엇인지 스스로에게 물어보십시오. 할 수 있습니까? 실제로 얼마나 자동화 될 것인지, 여전히 수동은 얼마입니까?

최고의 소원.

Answer 6

이것은 간단한 알고리즘에 효과가있을 수 있지만 o (n^2 lg n) 또는 o (n lg^2 n)는 어떻습니까?

시각적으로 쉽게 속일 수 있습니다.

그리고 그것이 정말로 나쁜 알고리즘이라면, 아마도 n = 10에서도 돌아 오지 않을 것입니다.

Answer 7

이것이 명확하지 않다는 증거 :

일부 기능 f에 대해 프로그램이 O (f (n))에서 멈췄는지 여부를 결정하는 알고리즘 Halts_in_fn (프로그램, 함수)이 있다고 가정 해 봅시다.

P는 다음 프로그램으로하자.

if(HALTS_IN_FN(P,f(n)))
{
    while(1);
}
halt;

함수와 프로그램이 고정되어 있으므로이 입력에 대한 Halts_in_FN은 일정한 시간입니다. halts_in_fn이 true를 반환하면 프로그램은 영원히 실행되며 물론 F (n)의 경우 O (f (n))에서 중단되지 않습니다. halts_in_fn이 false를 반환하면 프로그램이 O (1) 시간으로 중단됩니다.

따라서 우리는 역설과 모순이 있으므로 프로그램은 결정할 수 없습니다.

Answer 8

나는 이것을 자동으로하는 것이 거의 불가능하다고 생각합니다. O (g (n))은 최악의 상한이며 많은 기능이 많은 데이터 세트에서 그보다 더 잘 수행됩니다. 비교하려면 각각의 최악의 데이터 세트를 찾아야합니다. 많은 알고리즘에서는 그 자체로 어려운 작업입니다.

Answer 9

Jeffrey L Whitledge가 맞습니다. 중단 문제로부터 간단한 감소는 이것이 거절 할 수 없다는 것을 증명합니다 ...

또한이 프로그램을 쓸 수 있다면 P VS NP를 해결하는 데 사용하고 1 백만 달러가 있습니다 ... B-)

Answer 10

많은 사람들이 이것이 본질적으로 해결할 수없는 문제라고 언급했습니다. 충분히 공정하지만 그 이상으로, 심지어 가장 사소한 사례를 제외하고는 그것을 해결하는 것은 엄청나게 어려울 것 같습니다.

배열의 항목 수를 기반으로 한 중첩 루프 세트가있는 프로그램이 있다고 가정 해 봅시다. o (n^2). 그러나 내부 루프가 매우 구체적인 상황에서만 실행된다면 어떻게해야합니까? 평균적으로 Aprox Log (N) 사례로 실행됩니다. 갑자기 우리의 "명백히"O (n^2) 알고리즘은 실제로 O (n log n)입니다. 내부 루프가 실행되는지 여부를 결정할 수있는 프로그램을 작성하는 것은 원래 문제보다 잠재적으로 더 어려운 일입니다.

O (n)을 기억하십시오. 높은 상수는 경기장을 변화시킬 수 있습니다. QuickSort 알고리즘은 물론 O (N Log N)이지만 재귀가 충분히 작아지면 20 개 항목까지 내려 가면 많은 QuickSort 구현이 전술을 별도의 알고리즘으로 변경하여 실제로 다른 유형의 종류를 더 빠르게 수행 할 수 있습니다. , 삽입은 O (N)가 나쁘지만 훨씬 더 작은 상수를 지정합니다.

따라서 데이터를 이해하고 교육받은 추측을하고 테스트하십시오.

Answer 11

글쎄, 당신은 기능이 중단되는지 여부를 증명할 수 없기 때문에, 나는 당신이 조금 많이 요구한다고 생각합니다.

그렇지 않으면 @godeke가 가지고 있습니다.

Answer 12

그러한 벤치 마크를 실행할 때도주의를 기울여야합니다. 일부 알고리즘은 입력 유형에 크게 의존하는 동작을 갖습니다.

예를 들어 QuickSort를 사용하십시오. 최악의 O (N²)이지만 일반적으로 O (Nlogn)입니다. 같은 크기의 두 입력.

여행 세일즈맨은 (확실하지 않다고 생각합니다) o (n²) (편집 : 올바른 값은 Brute Force Algotithm의 경우 0 (n!)입니다.), 그러나 대부분의 알고리즘은 다소 근사한 솔루션이 훨씬 빨라집니다.

이는 벤치마킹 구조가 대부분의 시간을 임시로 적용해야 함을 의미합니다. 언급 된 두 가지 예에 대해 일반적인 것을 쓰는 것을 상상해보십시오. 그것은 매우 복잡하고 아마 사용할 수 없을 것이며 어쨌든 잘못된 결과를 얻을 수 있습니다.

Answer 13

입력의 유형과 구조가 함수간에 크게 다르기 때문에 이것이 완전 자동 방식으로 불가능하다고 생각합니다.

Answer 14

나는 이것을 할 때 당신의 목표가 무엇인지 모르겠지만, 우리는 내가 가르치는 과정에서 비슷한 문제가있었습니다. 학생들은 특정 복잡성에서 작동하는 것을 구현해야했습니다.

솔루션을 수동으로 살펴보고 코드를 읽지 않기 위해 @godeke가 제안한 방법을 사용했습니다. 목표는 Balansed Search Tree 대신 링크 된 목록을 사용한 학생 또는 Heap Sort 대신 Bubble Sort를 구현 한 학생들을 찾는 것이 었습니다 (즉, 필요한 복잡성에서는 작동하지 않지만 실제로 코드를 읽지 않고 구현).

놀랍게도, 결과는 속임수를 쓴 학생들을 밝히지 않았습니다. 우리 학생들이 정직하고 배우고 싶어하기 때문일 수 있습니다 (또는 우리가 이것을 확인할 것이라는 것을 알았습니다 ;-)). 입력이 작거나 입력 자체가 주문한 경우 부정 행위 학생을 놓칠 수 있습니다. 속임수를 쓰지 않았지만 상수 가치가 큰 학생들에 대해서는 잘못 될 수도 있습니다.

그러나 가능한 오류에도 불구하고, 많은 점검 시간을 절약하기 때문에 그만한 가치가 있습니다.

Answer 15

다른 사람들이 말했듯이, 이것은 이론적으로 불가능합니다. 그러나 실제로는 당신입니다 ~할 수 있다 함수가 O인지에 대한 교육받은 추측을하십시오 (N) 또는 O (N^2), 때때로 잘못을 신경 쓰지 않는 한.

알고리즘이 처음으로 다양한 입력에 실행됩니다. N. a에 포인트를 표시하십시오 로그 로그 그래프. 포인트를 통해 가장 적합한 선을 그립니다. 라인이 모든 포인트에 잘 맞으면 데이터는 알고리즘이 O (O)임을 시사합니다.N^케이), 어디 케이 선의 경사입니다.

나는 통계 학자가 아닙니다. 당신은이 모든 것을 소금 한 알로 가져 가야합니다. 그러나 실제로 성능 회귀를위한 자동 테스트의 맥락 에서이 작업을 수행했습니다. 여기 패치 일부 JS 코드가 포함되어 있습니다.

Answer 16

나는 a를 사용하고있다 big_O 도서관 (여기 링크) 독립 변수에 대한 실행 시간의 변경에 맞습니다. n 성장 계급의 순서를 추론합니다 O().

패키지는 각 클래스 성장 동작에 대한 수집 된 데이터로부터의 잔차를 측정하여 최상의 피팅 클래스를 자동으로 제안합니다.

코드를 확인하십시오 이 답변.

출력의 예,

Measuring .columns[::-1] complexity against rapid increase in # rows
--------------------------------------------------------------------------------
Big O() fits: Cubic: time = -0.017 + 0.00067*n^3
--------------------------------------------------------------------------------
Constant: time = 0.032                                        (res: 0.021)
Linear: time = -0.051 + 0.024*n                               (res: 0.011)
Quadratic: time = -0.026 + 0.0038*n^2                         (res: 0.0077)
Cubic: time = -0.017 + 0.00067*n^3                            (res: 0.0052)
Polynomial: time = -6.3 * x^1.5                               (res: 6)
Logarithmic: time = -0.026 + 0.053*log(n)                     (res: 0.015)
Linearithmic: time = -0.024 + 0.012*n*log(n)                  (res: 0.0094)
Exponential: time = -7 * 0.66^n                               (res: 3.6)
--------------------------------------------------------------------------------

Answer 17

균질 한 계산 자원이 많이 있다면 여러 샘플에 대해 시간을내어 선형 회귀를 수행 한 다음 가장 높은 용어를받습니다.

Answer 18

표시를 쉽게 얻을 수 있습니다 (예 : "함수는 선형? 하위 선형? 다항식? 지수")).

정확한 복잡성을 찾기가 어렵습니다.

예를 들어, 파이썬 솔루션은 다음과 같습니다. 함수와 크기 n의 매개 변수를 생성하는 함수를 제공합니다. 당신은 (n, 시간) 값 목록을 플롯하거나 수행 할 수 있습니다. 회귀 분석. 그것은 속도를 위해 한 번, 환경 요인의 간섭을 최소화하기 위해 여러 번 시간을 가야한다는 사실을 알기 위해서는 한 번입니다. 시간대 기준 치수).

import time
def measure_run_time(func, args):
  start = time.time()
  func(*args)
  return time.time() - start

def plot_times(func, generate_args, plot_sequence):
  return [
    (n, measure_run_time(func, generate_args(n+1)))
    for n in plot_sequence
  ]

그리고 시간에 버블 정렬에 사용하기 위해 :

def bubble_sort(l):
  for i in xrange(len(l)-1):
    for j in xrange(len(l)-1-i):
      if l[i+1] < l[i]:
        l[i],l[i+1] = l[i+1],l[i]

import random
def gen_args_for_sort(list_length):
  result = range(list_length) # list of 0..N-1
  random.shuffle(result) # randomize order
  # should return a tuple of arguments
  return (result,)

# timing for N = 1000, 2000, ..., 5000
times = plot_times(bubble_sort, gen_args_for_sort, xrange(1000,6000,1000))

import pprint
pprint.pprint(times)

이것은 내 컴퓨터에 인쇄되었습니다 :

[(1000, 0.078000068664550781),
 (2000, 0.34400010108947754),
 (3000, 0.7649998664855957),
 (4000, 1.3440001010894775),
 (5000, 2.1410000324249268)]