기술적으로 “Hello World”에 대한 O (1) 알고리즘입니까? System.Console.WriteLine(“It’s still not

이것이 “Hello, World!”에 대한 O (1) 알고리즘으로 분류됩니까? ??

public class Hello1
{
   public static void Main()
   {
      DateTime TwentyYearsLater = new DateTime(2035,01,01);
      while ( DateTime.Now < TwentyYearsLater )
      {
          System.Console.WriteLine("It's still not time to print the hello ...");
      }
      System.Console.WriteLine("Hello, World!");
   }
}

나는 사용을 생각하고있다 

DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{
   // ... 
}

누군가가 특정 복잡한 알고리즘을 요청할 때마다 농담으로 넣는 바쁜 루프로 코드 스 니펫. 이것이 맞습니까?

답변

이 컨텍스트에서 Big O 표기법은 함수 입력 크기와 해당 입력에 대한 결과를 계산하기 위해 수행해야하는 작업 수 간의 관계를 설명하는 데 사용됩니다.

작업에 출력과 관련 될 수있는 입력이 없으므로 Big O 표기법을 사용하는 것은 의미가 없습니다. 작업에 걸리는 시간은 작업 입력과 무관 합니다 (없음). 입력과 수행 된 작업 수간에 관계 가 없기 때문에 존재하지 않는 관계를 설명하는 데 Big O를 사용할 수 없습니다.

답변

Big-O 표기법은 대략 ‘작업량 N, 계산 시간, N에 비례하여 알고리즘에 걸리는 시간’을 대략적으로 의미합니다. 예를 들어, 크기가 N 인 배열을 정렬하는 것은 N ^ 2, Nlog (N) 등을 취할 수 있습니다.

여기에는 조치 할 입력 데이터가 없습니다. 그래서 그것은 아닙니다 O(anything).

더 나쁘다. 이것은 기술적으로 알고리즘이 아닙니다. 알고리즘은 수학 함수의 값을 계산하는 방법입니다. 수학 함수는 하나의 입력에서 출력으로의 매핑입니다. 이것은 입력을받지 않고 아무것도 반환하지 않기 때문에 수학적 의미에서 함수가 아닙니다. wikipedia에서 :

알고리즘은 한정된 공간과 시간 내에서 함수를 계산하기 위해 잘 정의 된 공식 언어로 표현할 수있는 효과적인 방법입니다. 초기 상태 및 초기 입력 (비어있을 수 있음)에서 시작하여 명령어는 실행될 때 유한 한 수의 잘 정의 된 연속 상태를 진행하여 결국 “출력”을 생성하고 최종 종료 상태에서 종료되는 계산을 설명합니다.

이것은 기술적으로 제어 시스템입니다. wikipedia에서;

제어 시스템은 다른 장치 또는 시스템의 동작을 관리, 명령, 지시 또는 규제하는 장치 또는 장치 집합입니다.

수학적 기능과 알고리즘의 차이에 대한보다 심층적 인 답변을 원하는 사람들과 콘솔 출력, 그래픽 표시 또는 로봇 제어와 같은 부작용을 일으키는 컴퓨터의 더 강력한 능력을 원하는 사람들 을 위해이 문서를 읽으십시오. 강력한 교회 학습 가설

요약

계산 위치 계산의 고전적 관점은 입력 (합리적 숫자 또는 유한 문자열)을 출력으로의 폐쇄 형 변환으로 나타냅니다. 컴퓨팅의 대화 형 관점에 따르면 계산은 입력을 출력으로 변환하는 기능 기반이 아니라 지속적인 대화 형 프로세스입니다. 특히 외부 세계와의 통신은 계산 전이나 후에가 아니라 계산 중에 발생합니다. 이 접근 방식은 계산이 무엇이며 어떻게 모델링되는지에 대한 우리의 이해를 근본적으로 변화시킵니다.

상호 작용을 새로운 패러다임으로 받아들이는 것은 Turing Machines (TM)가 모든 계산을 캡처한다는 광범위한 믿음 인 Strong Church-Turing Thesis (SCT)에 의해 방해를 받고 있으므로 TM보다 표현력이 더 높은 계산 모델은 불가능합니다. 이 논문에서 우리는 SCT가 원래의 Church-Turing Thesis (CTT)를 Turing이 의도하지 않은 방식으로 재 해석한다는 것을 보여줍니다. 일반적으로 원본과 동등하다고 가정되는 것은 신화입니다. 우리는 SCT에 대한 광범위한 믿음에 대한 역사적 이유를 식별하고 분석합니다. 그것이 거짓임을 받아들이는 것만으로 상호 작용을 계산의 대안 적 패러다임으로 채택 할 수 있습니다.

답변

아니요, 코드의 시간 복잡성은 O(2^|<DeltaTime>|),

현재 시간의 적절한 코딩을 위해.
제 영어에 대해 먼저 사과하겠습니다.

CS에서 Big O의 정의 및 작동 방식

Big O 표기법 은 프로그램의 입력을 실행 시간과 연결하는 데 사용되지 않습니다 .
Big O 표기법은 엄격함을 남기고 두 양 의 점근 비율 을 표현하는 방법 입니다.

알고리즘 분석의 경우이 두 수량은 입력 (먼저 “측정”기능이 있어야 함) 및 실행 시간 이 아닙니다 .
이는 문제 1 의 인스턴스 코딩 길이 와 관심 메트릭입니다.

일반적으로 사용되는 측정 항목은 다음과 같습니다.

  1. 주어진 계산 모델에서 알고리즘을 완료하는 데 필요한 단계 수입니다.
  2. 그러한 개념이있는 경우 계산 모델에 필요한 공간입니다.

암시 적으로 TM을 모델로 가정하여 첫 번째 지점 은 전환 2 기능 , 즉 “단계” 의 응용 프로그램 수로 변환되고 두 번째 지점 은 적어도 한 번 기록 된 서로 다른 테이프 셀 의 수를 변환합니다 .

또한 원래의 인코딩 대신 다 항적으로 관련된 인코딩을 사용할 수 있다고 암시 적으로 가정하는 경우가 있습니까? 예를 들어 배열을 처음부터 끝까지 검색하는 함수 O(n)는 이러한 배열의 인스턴스 코딩이 다음 길이를 가져야한다는 사실에도 불구하고 복잡합니다. 각 요소의 (상수) 기호 수는 n*b+(n-1)어디에 있습니까 b? 이는 b계산 모델의 상수로 간주되므로 위의 표현식과 n점근 적으로 동일하기 때문입니다.

등의 알고리즘 이유도 설명 평가판 부문 입니다 지수 기본적으로 인에도 불구하고 알고리즘 for(i=2; i<=sqr(N); i++)알고리즘과 같은 3 .

참조 이 .

이것은 또한 big O 표기법이 문제를 설명하는 데 필요한만큼의 매개 변수를 사용할 수 있음을 의미합니다 . 일부 알고리즘에 대해 k 매개 변수 를 갖는 것은 드문 일이 아닙니다 .

따라서 이것은 “입력”또는 “입력이 없음”에 관한 것이 아닙니다 .

지금 연구 사례

Big O 표기법은 알고리즘에 의문을 제기하는 것이 아니라 수행중인 작업을 알고 있다고 가정합니다. 그것은 본질적으로 모든 곳에서 적용 가능한 도구이며, 심지어 당신과 같이 의도적으로 까다로울 수있는 알고리즘에도 적용됩니다.

문제를 해결하기 위해 현재 날짜와 미래 날짜를 사용 했으므로 어떻게 든 문제의 일부가되어야합니다. 간단히 말해서, 그것들은 문제의 일부입니다.

특히 인스턴스는 다음과 같습니다.

<DeltaTime>

여기서는 <>선택의 비 병리 적 코딩을 의미합니다.

매우 중요한 설명 은 아래를 참조하십시오 .

따라서 O(2^|<DeltaTime>|)현재 시간의 값에 따라 많은 반복을 수행하기 때문에 큰 O 복잡도 시간은 단지 입니다. 점근 표기법이 상수를 제거하므로 유용하므로 다른 숫자 상수를 넣는 것은 의미가 없습니다 (예를 들어의 사용 O(10^|<DeltaTime>|*any_time_unit)은 무의미합니다).

까다로운 부분은

우리는 위에서 한 가지 중요한 가정을했습니다 : 계산 모델이 5 번 반복되고 시간이란 (실제?) 물리적 시간을 의미합니다. 표준 계산 모델에는 그러한 개념이 없습니다. TM은 시간을 알지 못합니다 . 이것이 우리의 현실이 작동하는 방식이기 때문에 시간을 단계 수와 연결합니다 4 .

모델에서 시간은 계산의 일부이지만 Main은 순수하지 않지만 개념은 동일하다고 말하여 기능적 사람들의 용어를 사용할 수 있습니다.

이것을 이해하려면 프레임 워크가 실제 시간보다 두 배, 다섯 배, 열 배 빠른 가짜 시간을 사용하는 것을 막을 수있는 것은 없습니다. 이렇게하면 코드가 “시간”의 “절반”, “1/5”, “1/10″에 실행됩니다.

이 반영은의 인코딩을 선택하는 데 중요합니다. 이것은 <DeltaTime>본질적으로 <(CurrentTime, TimeInFuture)>를 작성하는 압축 된 방법입니다. 시간이 수도회에 존재하지 않는 때문에, currentTime을의 코딩 아주 잘 단어 수 이제 (또는 다른 선택) 전날으로 코딩 할 수 어제 ,이 가정을 파괴함으로써 그 코딩의 길이를 증가 물리적 시간과 앞으로 이동 (그리고 DeltaTime 중 하나가 감소 함)

유용한 작업을 수행하려면 계산 모델에서 시간을 적절하게 모델링해야합니다.

우리가 할 수있는 유일한 안전한 선택은 물리적 시간이 진행됨에 따라 증가하는 길이 (하지만 여전히 단항을 사용하지 않음)로 타임 스탬프를 인코딩하는 것입니다. 이것은 우리가 필요로하는 유일한 진정한 시간 속성이며 인코딩이 포착해야하는 속성입니다. 알고리즘에 시간 복잡성이 주어질 수있는 것은 이러한 유형의 인코딩에서만 가능합니까?

혼동이 있다면 ‘ 시간 복잡성 은 무엇입니까 ?’라는 문구에서 시간 이라는 단어가 있다는 사실에서 발생합니다. 그리고 ‘얼마나 시간 이 걸릴까요?’ 매우 다른 것을 의미합니다

아아, 용어는 같은 단어를 사용하지만 머리 속에 “단계 복잡성”을 사용하여 자신에게 다시 질문 할 수 있습니다. 답이 실제로 ^ _ ^임을 이해하는 데 도움이되기를 바랍니다.

1 이것은 또한 각 인스턴스가 다르지만 임의적이지 않은 길이를 가지므로 점근 적 접근의 필요성을 설명합니다.
2 여기서 올바른 영어 용어를 사용하고 있기를 바랍니다.
3 또한 이것이 우리 log(log(n))가 수학에서 종종 용어를 찾는 이유 입니다.
4 Idest, 단계는 유한하지만 null이 아니거나 연결되지 않은 시간 간격을 차지해야합니다.
5 이것은 물리적 시간에 대한 지식으로서의 계산 모드, 즉 용어로 표현할 수 있음을 의미합니다. 비유는 제네릭이 .NET 프레임 워크에서 작동하는 방식입니다.

답변

여기에 훌륭한 답변이 많이 있지만 모두 조금 다시 말하겠습니다.

Big-O 표기법은 함수 를 설명하기 위해 존재 합니다 . 알고리즘 분석에 적용 할 때 먼저이 알고리즘의 일부 특성을 함수 측면에서 정의해야 합니다 . 일반적인 선택은 입력 크기 의 함수로 단계 수를 고려 하는 것입니다 . 다른 답변에서 언급했듯이 명확하게 정의 된 “입력”이 없기 때문에 귀하의 경우에 그러한 기능을 생각해내는 것이 이상하게 보입니다. 그래도 시도 할 수 있습니다.

  • 우리는 당신의 알고리즘을 어떤 크기의 입력이든 받아들이고, 그것을 무시하고, 고정 된 시간 동안 기다렸다가 끝나는 상수 함수로 간주 할 수 있습니다. 이 경우 런타임은 f (n) = const 이고 O (1) 시간 알고리즘입니다. 이것은 당신이 듣기를 기대했던 것입니다. 예, 기술적으로 O (1) 알고리즘 입니다.
  • 관심있는 TwentyYearsLater“입력 크기”와 유사한 매개 변수로 간주 할 수 있습니다 . 이 경우 런타임은 f (n) = (nx)입니다. 여기서 x 는 호출 시점의 “현재 시간”입니다. 이런 식으로 보면 O (n) 시간 알고리즘입니다. 기술적으로 O (1) 알고리즘 을 다른 사람들에게 보여줄 때마다이 반론을 기대하십시오 .
  • 오,하지만 k =TwentyYearsLater 가 입력이라면 그 크기 n 은 실제로 그것을 나타내는 데 필요한 비트 수입니다. 즉, n = log (k) 입니다. 따라서 입력 n 의 크기 와 런타임 간의 종속성은 f (n) = 2 ^ n-x 입니다. 알고리즘이 기하 급수적으로 느려진 것 같습니다! 으.
  • 프로그램에 대한 또 다른 입력은 실제로 OS가 루프 의 호출 시퀀스에 대해 제공하는 응답 스트림입니다DateTime.Now . 실제로이 전체 시퀀스가 ​​프로그램을 실행하는 순간 입력으로 제공된다고 상상할 수 있습니다. 그런 다음 런타임은이 시퀀스의 속성, 즉 첫 번째 TwentyYearsLater요소 까지의 길이에 의존하는 것으로 간주 할 수 있습니다 . 이 경우 런타임은 다시 f (n) = n 이고 알고리즘은 O (n) 입니다.

그러나 다시 질문에서 런타임에 관심이 있다고 말하지 않았습니다. 메모리 사용을 의미한다면? 상황을 모델링하는 방법에 따라 알고리즘이 O (1)-메모리 또는 아마도 O (n)-메모리라고 말할 수 있습니다 DateTime.Now.

그리고 당신의 목표가 어리석은 것을 생각해내는 것이었다면, 화면에서 알고리즘 코드의 크기 (픽셀 단위)가 선택한 확대 / 축소 수준에 따라 달라지는 방식에 관심이 있다고 말하십시오. 이것은 f (zoom) = 1 / zoom 과 같을 수 있으며 알고리즘을 O (1 / n) 픽셀 크기로 자랑스럽게 선언 할 수 있습니다 !

답변

나는 Servy에 약간 동의하지 않습니다. 이 프로그램에 대한 입력은 명확하지 않더라도 시스템의 시간입니다. 이것은 의도하지 않은 기술 일 수 있지만 TwentyYearsFromNow변수는 현재 시스템 시점 에서 20 년이 아닙니다. 2035 년 1 월 1 일에 정적으로 할당됩니다.

따라서이 코드를 가져 와서 시스템 시간이 1970 년 1 월 1 일인 시스템에서 실행하면 컴퓨터의 속도에 관계없이 완료하는 데 65 년이 걸릴 것입니다 (시계에 결함이있는 경우 약간의 차이가있을 수 있음). ). 이 코드를 가져 와서 시스템 시간이 2035 년 1 월 2 일인 시스템에서 실행하면 거의 즉시 완료됩니다.

귀하의 의견 n은 다음과 같습니다.January 1st, 2035 - DateTime.Now , 그리고 그것의 O (N).

그리고 작업 횟수 문제도 있습니다. 어떤 사람들은 더 빠른 컴퓨터가 더 빨리 루프에 도달하여 더 많은 작업을 유발한다고 지적했지만 이는 관련이 없습니다. big-O 표기법으로 작업 할 때 프로세서의 속도 나 정확한 작업 수를 고려하지 않습니다. 이 알고리즘을 컴퓨터에서 실행 한 다음 다시 실행했지만 동일한 컴퓨터에서 10 배 더 오래 실행하면 작업 수가 10 배의 동일한 요소로 증가 할 것으로 예상됩니다.

이것에 관해서 :

나는 누군가가 특정 복잡한 알고리즘을 요청할 때마다 농담으로 넣는 바쁜 루프로 코드의 [편집 된 코드] 스 니펫을 사용할 생각입니다. 이것이 맞습니까?

아니 정말. 다른 답변에서 이것을 다루었으므로 언급하고 싶었습니다. 일반적으로 수년간의 실행을 big-O 표기법과 연관시킬 수 없습니다. 예 : 20 년의 처형 = O (n ^ 87) 또는 그 문제에 대해 다른 어떤 것도 말할 방법이 없습니다. 당신이 준 알고리즘에서도 TwentyYearsFromNow20110, 75699436 또는 123456789로 변경할 수 있고 big-O는 여전히 O (n)입니다.

답변

Big-O 분석은 처리되는 데이터의 양이 제한없이 증가함에 따라 관련된 처리량을 다룹니다.

여기에서는 실제로 고정 된 크기의 단일 개체 만 처리합니다. 따라서 big-O 분석을 적용하는 것은 용어를 정의하는 방법에 따라 크게 달라집니다 (주로?).

예를 들어, 일반적으로 출력물을 인쇄하고 합리적인 양의 데이터가 정확히 동일한 기간에 인쇄 될 수 있도록 너무 오래 기다려야 함을 의미 할 수 있습니다. 또한 매우 멀리 떨어지려면 다소 비정상적인 (완전히 잘못되지는 않았더라도) 정의를 조금 더 추가해야합니다. 특히 big-O 분석은 일반적 으로 작업을 수행하는 데 필요한 기본 작업 수로 정의됩니다. 특정 작업 (하지만 CPU 사용 / 수행 된 작업뿐만 아니라 메모리 사용과 같은 측면에서도 복잡성을 고려할 수 있음).

기본 작업의 수는 일반적으로 소요 시간에 상당히 가깝게 변환되므로 두 가지를 동의어로 취급하는 것은 큰 무리가 아닙니다. 그러나 불행히도 우리는 처리되는 데이터의 양이 제한없이 증가한다는 다른 부분에 여전히 고착되어 있습니다. 그렇기 때문에 사용자가 부과 할 수있는 고정 지연은 실제로 작동하지 않습니다. O (1)을 O (N)과 동일시하려면, 무한한 양의 데이터처럼 고정 된 양의 데이터를 인쇄하는 데 영원히 걸리도록 무한 지연을 부과해야합니다.

답변

무엇에 대한 빅오?

당신은 그것이 twentyYearsLater“입력”이라고 직관하는 것 같습니다 . 실제로 함수를 다음과 같이 작성했다면

void helloWorld(int years) {
   // ...
}

N = 연도 (또는 그냥 O(years) ) 인 )입니다.

나는 당신의 알고리즘이 twentyYearsLater =.로 시작하는 코드 줄에 쓰는 숫자와 관련하여 O (N)이라고 말할 것입니다 . 그러나 사람들은 일반적으로 실제 소스 코드의 숫자를 입력으로 간주하지 않습니다. 그들은 명령 줄 입력을 입력으로 간주하거나 함수 서명 입력을 입력으로 간주 할 수 있지만 소스 코드 자체는 아닐 가능성이 높습니다. 그것이 당신이 친구와 이의를 제기하는 것입니다. 이것이 “입력”입니까? 직관적으로 입력처럼 보이도록 코드를 설정하고 프로그램의 6 행에있는 숫자 N과 관련하여 큰 O 실행 시간을 물을 수 있지만 기본이 아닌 선택을 사용하는 경우 입력으로 당신은 정말로 그것에 대해 명시해야합니다.

그러나 입력을 명령 줄이나 함수에 대한 입력과 같이 더 일반적인 것으로 취하면 출력이 전혀없고 함수는 O (1)입니다. 20 년이 걸리지 만 big-O는 상수 배수로 변하지 않기 때문에 O (1) = O (20 년)입니다.

비슷한 질문-런타임은 무엇입니까?

void sortArrayOfSizeTenMillion(int[] array)

그것이 말하는 것을 수행하고 입력이 유효하고 알고리즘이 퀵 정렬 또는 버블 정렬 또는 합리적인 모든 것을 활용한다고 가정하면 O (1)입니다.