알고리즘을 사용한 작업을 통해 수년 동안 알고리즘의 점근 적 동작에 관한 질문이 생겼습니다.행렬을 입력으로 사용하는 알고리즘의 큰 O 표기법
수학에서는 Big-W (hatever)를 "입력 크기 'n'에 대해 측정 한 f (n)의 점근 적 거동으로 정의 할 수 있습니다." 내 마음에 오는 큰-O의 정의는 (의역)된다
In order for f(n) to be O(g(n)) we need to find a constant that multiplied by g(n) the expression 'f(n) < c*g(n)' from an initial input (i.e. n0) and forever.
우리가 볼 수 있듯이, 모든 것이 'N'(입력)에 따라 측정된다.
내 질문은 알고리즘의 입력 크기가 매트릭스 (자체가 이미 제곱) 인 경우 두 개의 중첩 된 'for'루프를 사용하여이를 트래버스하는 경우 알고리즘이 여전히 O (n) 알고리즘?
예 :
1 1 1 1 0 1
2 2 0 2 1 0
3 3 1 3 2 1
0 4 2 4 3 2
1 5 3 5 4 0
2 6 0 6 5 1
for(var row=0; row<matrix.rows; row++){
...
for(var col=0; col<matrix.columns; col++){
...
}
}
내 로직이이 O 인 것을 나 지시 (N^2) 그러나 수학 매우 다르며 동작은 입력 크기에 따라 측정된다. 이것이 O (n^2)이면 괜찮습니다. 그러나 내가 혼란스럽게 여기는 것은 다른 관점에서 문제를 보았을 때 나에게 엉망이되어 버린다는 것입니다. 행을 탐색하는 경우 알고리즘의 입력이 cols * rows (행렬)이고 내가 행을 가로 지르면서 O (log (n))로 동작한다고 말할 수 있습니다.
누군가이 작품과 같은 것을 설명 할 수 있습니까? 그것은 O (n) 또는 O (n^2)일까요? 다른 크기 (예 : 큐브 등)에서 동일합니까?
P. 나는 내가 자신을 올바르게 설명했기를 바란다.