O (1 / n) 알고리즘이 있습니까?
O (1 / n) 알고리즘이 있습니까?
아니면 O (1)보다 작은 것이 있습니까?
이 질문은 생각보다 어리석지 않습니다. 이론적으로, O (1 / n ) 과 같은 것은 Big O 표기법 의 수학적 정의를 취할 때 완전히 의미가 있습니다 .
이제 g ( x )를 1 / x로 쉽게 대체 할 수 있습니다 . 위의 정의는 여전히 일부 f에 대한 것 입니다.
점근 적 런타임 성장을 추정하기 위해 이것은 실행 가능성이 낮습니다. 입력이 증가함에 따라 의미있는 알고리즘이 더 빨라질 수 없습니다. 물론이를 수행하기 위해 임의의 알고리즘을 구성 할 수 있습니다 (예 : 다음 알고리즘).
def get_faster(list):
how_long = (1 / len(list)) * 100000
sleep(how_long)
분명히,이 함수는 입력 크기가 커질수록 시간이 덜 걸립니다. 적어도 하드웨어에 의해 시행되는 제한 (수의 정밀도, sleep기다릴 수있는 최소 시간 , 인수 처리 시간 등)까지 :이 제한은 다음과 같습니다. 상수 하한이므로 실제로 위 함수는 여전히 런타임 O (1)을 갖습니다 .
그러나 거기에 있는 런타임 (적어도 부분적) 줄일 수 있습니다 사실 실제 알고리즘 입력 크기가 증가합니다. 그러나 이러한 알고리즘은 O (1) 미만의 런타임 동작을 나타내지 않습니다 . 여전히 그들은 흥미 롭습니다. 예를 들어 Horspool 의 매우 간단한 텍스트 검색 알고리즘을 사용 하십시오 . 여기서는 검색 패턴의 길이가 증가함에 따라 예상 런타임이 감소하지만 건초 더미의 길이가 증가하면 런타임이 다시 증가합니다.
예.
"빈"알고리즘 인 런타임 O (1 / n)의 알고리즘이 정확히 하나 있습니다.
알고리즘이 O (1 / n)이면 단일 명령으로 구성된 알고리즘보다 적은 단계로 무조건 실행됩니다. 모든 n> n0에 대해 한 단계보다 적은 단계로 실행되는 경우 해당 n에 대한 명령이 전혀 없어야합니다. 'n> n0'인 경우 적어도 하나의 명령 비용이 발생하므로 모든 n에 대한 명령이 없어야합니다.
요약 : O (1 / n) 인 유일한 알고리즘은 명령 이 없는 빈 알고리즘 입니다.
그건 불가능하다. Big-O의 정의는 불평등 보다 크지 않습니다 .
A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)
따라서 B (n)은 실제로 최대 값이므로 n이 증가함에 따라 감소하면 추정값은 변하지 않습니다.
sharptooth가 정확하고 O (1)이 최상의 성능입니다. 그러나 빠른 솔루션이 아니라 고정 된 시간 솔루션을 의미합니다.
흥미로운 변형과 아마도 실제로 제안 되는 것은 인구가 증가함에 따라 어떤 문제가 더 쉬워 지는지입니다 . 나는 생각하고 뺨에 혀로 대답하지만 1을 생각할 수 있습니다.
세트에있는 두 사람이 같은 생일을 가지고 있습니까? n이 365를 초과하면 true를 반환합니다. 365 미만이지만 이것은 O (n ln n)입니다. 문제가 서서히 쉬워지지 않고 n> 365의 경우 O (1)이되기 때문에 아마도 큰 대답은 아닙니다.
이전의 큰 O 표기법 학습에서 1 단계 (예 : 변수 확인, 할당 수행)가 필요한 경우에도 O (1)입니다.
"상수"는 중요하지 않기 때문에 O (1)은 O (6)과 동일합니다. 그래서 O (n)은 O (3n)과 동일합니다.
따라서 1 단계가 필요하면 O (1)입니다 ... 프로그램에는 적어도 1 단계가 필요하므로 알고리즘의 최소 단계는 O (1)입니다. 우리가하지 않으면 O (0)입니다. 우리가 전혀 아무것도하지 않는다면, 그것은 O (1)이며, 그것이 할 수있는 최소값입니다.
(그렇지 않으면 Zen 또는 Tao 질문이 될 수 있습니다 ... 프로그래밍 영역에서 O (1)은 여전히 최소입니다).
아니면 어떻습니까?
프로그래머 : 보스, O (1) 시간 안에 할 수있는 방법을 찾았습니다!
보스 : 오늘 아침에 파산합니다.
프로그래머 : 아, 그러면 O (0)이됩니다.
아니요, 불가능합니다 :
n은 1 / n에서 무한대 인 경향이 있으므로 결국 우리는 1 / (inf)를 달성하는데, 이는 사실상 0입니다.
따라서 문제의 큰 클래스는 거대한 n을 가진 O (0)이지만 낮은 n을 가진 일정한 시간에 더 가깝습니다. 일정한 시간보다 빠르게 수행 할 수있는 유일한 방법은 다음과 같습니다.
void nothing() {};
그리고 이것조차도 논쟁의 여지가 있습니다!
명령을 실행하자마자 최소한 O (1)에 도달 했으므로 O (1 / n)의 큰 클래스를 가질 수 없습니다!
기능을 전혀 실행하지 않는 것은 어떻습니까 (NOOP)? 또는 고정 된 값을 사용합니다. 그게 중요합니까?
나는 종종 입력이 커질수록 작아지는 확률을 설명하기 위해 O (1 / n)을 사용합니다. 예를 들어, 공정한 동전이 log2 (n) 플립에서 꼬리가 올 확률은 O (1 / n)입니다.
O (1)은 단순히 "일정한 시간"을 의미합니다.
루프 [1]에 초기 종료를 추가하면 O (1) 알고리즘을 O (n)으로 바꾸지 만 더 빠르게 만듭니다.
트릭은 일반적 으로 일정 시간 알고리즘이 최고이며 선형보다 지수보다 낫지 만 n이 소량 인 경우 지수 알고리즘이 실제로 더 빠를 수 있습니다.
1 :이 예제의 정적 목록 길이 가정
양자 알고리즘이 중첩을 통해 "한 번에"여러 계산을 수행 할 수 있다고 생각합니다 ...
이것이 유용한 답변인지 의심합니다.
이 질문을 읽고 대화 내용을 이해하려는 사람은 다음과 같이 도움이 될 수 있습니다.
| |constant |logarithmic |linear| N-log-N |quadratic| cubic | exponential |
| n | O(1) | O(log n) | O(n) |O(n log n)| O(n^2) | O(n^3) | O(2^n) |
| 1 | 1 | 1 | 1| 1| 1| 1 | 2 |
| 2 | 1 | 1 | 2| 2| 4| 8 | 4 |
| 4 | 1 | 2 | 4| 8| 16| 64 | 16 |
| 8 | 1 | 3 | 8| 24| 64| 512 | 256 |
| 16 | 1 | 4 | 16| 64| 256| 4,096 | 65536 |
| 32 | 1 | 5 | 32| 160| 1,024| 32,768 | 4,294,967,296 |
| 64 | 1 | 6 | 64| 384| 4,069| 262,144 | 1.8 x 10^19 |
많은 사람들이 정답을 얻었습니다. (아니오) 그것을 증명하는 또 다른 방법이 있습니다. 함수를 가지려면 함수를 호출해야하며 답을 반환해야합니다. 일정한 시간이 걸립니다. 심지어 나머지 처리 시간이 더 큰 입력에 더 적은 시간이 걸리더라도 응답을 인쇄하는 경우 (단일 비트라고 가정 할 수 있음) 최소한 일정한 시간이 걸립니다.
솔루션이 존재하면 즉시 일정한 시간에 준비하여 액세스 할 수 있습니다. 예를 들어 정렬 쿼리가 역순임을 알고있는 경우 LIFO 데이터 구조를 사용합니다. 그런 다음 적절한 모델 (LIFO)을 선택하면 데이터가 이미 정렬됩니다.
인구가 증가함에 따라 어떤 문제가 더 쉬워 집니까? 하나의 대답은 다운로드 속도가 노드 수의 역함수 인 비트 토렌트와 같은 것입니다. 자동차와 달리, 더 많이 적재할수록 속도가 느려지는 반면, 비트 토렌트와 같은 파일 공유 네트워크는 더 많은 노드를 연결합니다.
O (1) 아래로 갈 수는 없지만 k가 N보다 작은 O (k)는 가능합니다. 우리는 그것들을 sublinear time algorithms 라고 부릅니다 . 일부 문제에서 Sublinear time 알고리즘은 특정 문제에 대한 대략적인 솔루션 만 제공 할 수 있습니다. 그러나 때로는 대략적인 솔루션이 적합합니다. 아마도 데이터 세트가 너무 크거나 모두 계산하기에는 계산 비용이 너무 많이 들기 때문일 수 있습니다.
이건 어때?
void FindRandomInList(list l)
{
while(1)
{
int rand = Random.next();
if (l.contains(rand))
return;
}
}
목록의 크기가 커질수록 프로그램의 예상 런타임이 줄어 듭니다.
O (1 / n)은 O (1)보다 작지 않습니다. 기본적으로 데이터가 많을수록 알고리즘이 더 빠릅니다. 배열을 가져 와서 그 수가 적 으면 항상 최대 10100 개의 요소 를 채우고 더 많은 것이 없으면 아무것도하지 않는다고 가정 해보십시오. 이것은 물론 O (1 / n)은 아니지만 O (-n)과 같은 것입니다. :) 너무 나쁜 O- 큰 표기법은 음수 값을 허용하지 않습니다.
지적 된 바와 같이, 널 함수의 가능한 예외를 제외 O(1/n)하고, 걸리는 시간이 0에 접근해야하기 때문에 함수 가 없을 수있다 .
물론 Konrad에 의해 정의 된 것과 같은 알고리즘이 있는데, 이는 O(1)적어도 어떤 의미에서는 작아야하는 것처럼 보입니다 .
def get_faster(list):
how_long = 1/len(list)
sleep(how_long)
이러한 알고리즘을 조사하려면 고유 한 점근 측정 또는 시간 개념을 정의해야합니다. 예를 들어, 위의 알고리즘에서 여러 번의 "무료"작업을 정해진 횟수만큼 사용할 수 있습니다. 위의 알고리즘에서 수면 이외의 모든 시간을 제외하여 t '를 정의하면 t'= 1 / n, 즉 O (1 / n)입니다. 점근 적 행동이 사소한 것이므로 더 좋은 예가있을 것입니다. 사실, 나는 누군가가 사소한 결과를 낳는 감각을 생각 해낼 수 있다고 확신합니다.
나머지 답변의 대부분은 big-O를 알고리즘의 실행 시간에 대해서만 독점적으로 해석합니다. 그러나 그 질문에 대해 언급하지 않았기 때문에 수치 분석에서 big-O의 다른 적용, 즉 오류에 대해 언급 할 가치가 있다고 생각했습니다.
스텝 크기 (h) 또는 나눗셈 수 (n)에 대한 여부에 따라 많은 알고리즘이 O (h ^ p) 또는 O (n ^ {-p}) 일 수 있습니다. 예를 들어 Euler의 방법 에서 y (0) 및 dy / dx (y의 파생)를 알고 있으면 y (h)의 추정치를 찾습니다. y (h)의 추정치는 h가 0에 가까울수록 더 정확합니다. 따라서 임의의 x에 대해 y (x)를 찾으려면 0에서 x까지의 간격을 취하여 n 개까지 분할하고 Euler의 방법을 실행합니다 각 지점에서 y (0)에서 y (x / n)에서 y (2x / n)로 이동합니다.
따라서 Euler의 방법은 O (h) 또는 O (1 / n) 알고리즘입니다. 여기서 h는 일반적으로 단계 크기로 해석되고 n은 구간을 나누는 횟수로 해석됩니다.
부동 소수점 반올림 오차로 인해 실제 수치 분석 응용 프로그램에서 O (1 / h)를 가질 수도 있습니다 . 간격을 작게 만들수록 특정 알고리즘의 구현에서 더 많은 취소가 발생하고 유효 숫자가 더 많이 손실되므로 오류가 발생하여 알고리즘을 통해 전파됩니다.
Euler의 방법의 경우 부동 소수점을 사용하는 경우 작은 단계와 취소를 사용하고 큰 숫자에 작은 숫자를 추가하여 큰 숫자를 변경하지 마십시오. 부드러운 함수 y에서 y '(x)를 (y (x + h)-y (x) / h)로 근사한 두 개의 매우 가까운 위치에서 평가 된 함수에서 두 숫자를 빼서 미분을 계산하는 알고리즘의 경우 y (x + h)는 y (x)에 가까워 지므로 큰 취소가 발생하고 유의미한 수치가 적은 미분에 대한 추정치가 생성됩니다. 이는 파생 알고리즘이 필요한 알고리즘 (예 : 경계 값 문제)으로 전파됩니다.
좋아, 나는 그것에 대해 약간의 생각을했고, 아마도이 일반적인 형태를 따르는 알고리즘이있을 수 있습니다.
1000 노드 그래프에 대해 이동하는 판매원 문제를 계산해야하지만 방문 할 수없는 노드 목록도 제공됩니다. 방문 할 수없는 노드 목록이 커질수록 문제를 해결하기가 더 쉬워집니다.
상한에 O (1 / n) 알고리즘이 있음을 알 수 있습니다.
루틴 외부의 무언가로 인해 변경되는 일련의 입력이 있습니다 (하드웨어를 반영하거나 프로세서의 다른 코어 일 수 있음). 그러나 임의의 유효한 입력을 선택해야합니다.
이제 변경되지 않은 경우 단순히 항목 목록을 만들고 임의로 하나를 선택하고 O (1) 시간을 얻습니다. 그러나 데이터의 동적 특성으로 인해 목록을 만들 수 없으므로 무작위로 프로브하고 프로브의 유효성을 테스트하면됩니다. (그리고 본질적으로 답변이 반환 될 때 여전히 답이 유효하다는 보장은 없습니다. 이것은 여전히 게임에서 유닛의 AI를 사용할 수 있습니다. 방아쇠를 당기십시오.)
이는 최악의 경우 성능은 무한하지만 데이터 공간이 가득 차면 평균 성능은 저하됩니다.
수치 분석에서 근사 알고리즘은 근사 공차에서 일정하지 않은 점근 적 복잡성을 가져야합니다.
class Function
{
public double[] ApproximateSolution(double tolerance)
{
// if this isn't sub-constant on the parameter, it's rather useless
}
}
나는 O (1) 미만이 불가능하다고 생각합니다. algo가 사용하는 모든 시간을 O (1)이라고합니다. 그러나 O (1 / n)의 경우 아래 함수는 어떻습니까? (이 솔루션에는 이미 많은 변형이 있음을 알고 있지만 모두 결함이 있다고 생각합니다 (주요한 것이 아니라 개념을 잘 설명합니다). 여기에 논쟁의 여지가 있습니다.
def 1_by_n(n, C = 10): #n could be float. C could be any positive number
if n <= 0.0: #If input is actually 0, infinite loop.
while True:
sleep(1) #or pass
return #This line is not needed and is unreachable
delta = 0.0001
itr = delta
while delta < C/n:
itr += delta
따라서 n이 증가함에 따라 함수 시간이 점점 줄어 듭니다. 또한 입력이 실제로 0이면 함수를 반환하는 데 시간이 오래 걸리지 않습니다.
기계의 정밀도에 의해 제한 될 것이라고 주장 할 수 있습니다. 따라서 sinc eit는 상한을 가지며 O (1)입니다. 그러나 우리는 문자열에서 n과 C의 입력을 취함으로써 그것을 우회 할 수 있습니다. 그리고 덧셈과 비교는 문자열에서 수행됩니다. 아이디어는 이것으로 우리는 n을 임의로 줄일 수 있다는 것입니다. 따라서 n = 0을 무시하더라도 함수의 상한은 제한되지 않습니다.
또한 런타임이 O (1 / n)라고 말할 수는 없다고 생각합니다. 그러나 우리는 O (1 + 1 / n)과 같은 것을 말해야합니다
O (1 / n) 인 알고리즘을 구성 할 수 있습니다. 한 예는 f (n) -n 배의 일부 배수를 반복하는 루프입니다. 여기서 f (n)은 n보다 큰 값을 보장하는 함수이고 n이 무한대에 가까워 질수록 f (n) -n의 한계는 다음과 같습니다. 제로. f (n)의 계산은 모든 n에 대해 일정해야합니다. 나는 f (n)이 어떻게 보일지 또는 그러한 알고리즘이 어떤 응용 프로그램을 가질 것인지 알지 못하지만 그러한 기능은 존재할 수 있지만 결과 알고리즘은 알고리즘의 가능성을 증명하는 것 이외의 다른 목적을 가지고 있지 않습니다. O (1 / n).
알고리즘에 대해서는 모르지만 O (1) 미만의 복잡성은 무작위 알고리즘에 나타납니다. 실제로 o (1) (작은 o)는 O (1)보다 작습니다. 이러한 종류의 복잡성은 일반적으로 무작위 알고리즘에 나타납니다. 예를 들어, 당신이 말했듯이, 어떤 사건의 확률이 1 / n 순서 일 때, 그들은 o (1)로 표시합니다. 또는 높은 확률로 어떤 일이 발생한다고 말하고 싶을 때 (예 : 1-1 / n) 1-o (1)로 표시합니다.
입력 데이터에 관계없이 답이 동일하면 O (0) 알고리즘이 있습니다.
즉, 입력 데이터가 제출되기 전에 답이 알려짐-함수가 최적화 될 수 있음-O (0)
Big-O 표기법은 일반적인 런타임과 동일하지 않은 알고리즘 의 최악의 시나리오 를 나타냅니다 . O (1 / n) 알고리즘이 O (1) 알고리즘임을 증명하는 것은 간단합니다. 정의상,
O (1 / n)-> T (n) <= 1 / n, 모든 n> = C> 0
O (1 / n)-> T (n) <= 1 / C에 대해
Big-O 표기법은 상수를 무시하기 때문에 1 / n <= 1 / C 모든 n> = C O (1 / n)-> O (1) (즉, C 값은 중요하지 않음)
O (1)보다 작은 것은 없습니다. Big-O 표기법은 알고리즘의 가장 복잡한 복잡성을 의미합니다.
알고리즘의 런타임이 n ^ 3 + n ^ 2 + n + 5이면 O (n ^ 3)입니다. n-> Inf와 같이 n ^ 2는 다음과 관련이 없기 때문에 저전력은 전혀 중요하지 않습니다. n ^ 3
n-> Inf와 마찬가지로 O (1 / n)은 O (1)에 비해 관련이 없으므로 3 + O (1 / n)은 O (1)과 동일하므로 O (1)을 가장 작은 계산 가능 복잡성
inline void O0Algorithm() {}
간단한 O (1 / n) 알고리즘이 있습니다. 그리고 그것은 심지어 흥미로운 일을합니다!
function foo(list input) {
int m;
double output;
m = (1/ input.size) * max_value;
output = 0;
for (int i = 0; i < m; i++)
output+= random(0,1);
return output;
}
입력 크기가 커지면 함수의 출력이 어떻게 바뀌는지를 설명하므로 O (1 / n)이 가능합니다. 함수 1 / n을 사용하여 함수가 실행하는 명령어 수를 설명하는 경우 함수가 입력 크기에 대해 제로 명령어를 취할 필요는 없습니다. 오히려, 일부 임계 값을 초과하는 모든 입력 크기에 대해 필요한 명령의 수는 양의 상수에 1 / n을 곱한 값으로 제한됩니다. 1 / n이 0 인 실제 숫자가없고 상수가 양수이므로 함수가 0 개 이하의 명령을 수행하도록 제한 할 이유가 없습니다.
참고 URL : https://stackoverflow.com/questions/905551/are-there-any-o1-n-algorithms
'Programing' 카테고리의 다른 글
| Jackson의 ObjectMapper를 정적 필드로 선언해야합니까? (0) | 2020.03.05 |
|---|---|
| 자바와 SQLite (0) | 2020.03.05 |
| contenteditable 변경 이벤트 (0) | 2020.03.05 |
| 일부 HTML 태그에 대한 임의의 데이터를 저장하는 방법 (0) | 2020.03.05 |
| 파이썬 스크립트의 구문을 실행하지 않고 어떻게 확인할 수 있습니까? (0) | 2020.03.05 |