haein   5년 전

문제. 아래 알고리즘에 대한 복잡도 (big-O)를 구하라. (단, for loop의 조건 검사에 사용된 비교는 무시하라. a1, a2, ..., an은 양의 실수이고 max(aiaj, m)은 ai와 aj사이의 값과 m중에서 가장 큰 값을 찾는 함수이다.)

m <- 0

for i <- 1 to n

     for j <- i + 1 to n

          m <- max(aiaj, m)

저의 생각은 이러합니다. 해당 코드는 총 O(n^2)만큼 반복하며 매 반복시 max함수가 호출됩니다. max함수는 ai 와 aj 사이의 값들과 m값 중에서 최댓값을 찾는 함수이므로 해당 max함수의 시간복잡도는 O(n)입니다. 결과적으로 해당 알고리즘의 시간복잡도는 O(n^3)이라고 생각합니다. 

하지만 이에 대한 이견이 있습니다. max함수를 잘 정의하면 O(1)만에 위의 작업을 수행할 수 있으며 이러한 경우 위 알고리즘의 최종 시간복잡도가 O(n^2)이 됩니다. 저는 이러한 답변이 유효하려면 문제에서 max함수를 ai와 aj, m 중에 가장 큰 값을 찾는 함수라고 정의 했었어야 한다고 생각합니다.

하지만 제 생각에는 문제에 분명 max는 ai와 aj사이의 값들과 m중에서 최댓값을 반환하는 "함수"라고 기술 되어 있으며 max가 이러한 기능을 수행하는 함수라고 정의 되기 위해서는 어떠한 경우에서든 범위를 지정하는 두개의 인덱스 값과 한개의 m값을 받았을때 그중 가장 큰 최댓값을 반환할 수 있어야 된다고 생각합니다.  max함수를 O(1)만에 최댓값을 찾는 함수라고 가정한다면 이 함수는 더 이상 문제에서 설명한 기능을 실행하는 함수가 아니라고 생각합니다. O(1)이라고 정의된 max함수가 다른 경우에 호출되었을때 올바른 최댓값을 낼 수 없다면 이는 문제에서 정의된 max함수가 아니기 때문에 max함수를 O(1)이라고 판단하는 것은 문제에 대한 모순이라고 생각합니다.

다른 분들의 의견이 궁금합니다. 읽어주셔서 감사합니다.

djm03178   5년 전

'사이'라는 표현이 좀 애매하네요. 그 표현이 a의 i, i + 1, i + 2, ... j번째 중에서라는 표현이라면 O(n^3)이 맞겠지만, 그냥 ai aj라고만 했기 때문에 i번째 인덱스와 j번째 인덱스만을 고려하는 표현일 수도 있습니다. 애초에 a1 a2 a3를 '값'이라고 정의했기 때문에 ai, aj라는 표현을 쓴 순간에 이미 그들은 배열의 특정 위치를 나타내는 것이 아닌 그냥 개별적인 값이라고 이해할 수도 있습니다.

chogahui05   5년 전

답이 O(n^2)인가요? max 함수에 대한 설명 없이 답이 저렇게 나오는 건 이상합니다. 그리고 전처리 없이

i ~ j까지 구간에서 최대치를 구한다. 그러면 O(|j-i|)가 나올 거고요.

사실 더 생각을 해 본다면 ai ~ aj까지는 for i<-1 to n 안에 변수를 하나 초기화 시켜서 

관리하면 되기 때문에 O(1)로 줄일 순 있다고 생각합니다만.. 어디서 이런 문제를 냈는지도 모르겠고..

문제가 저게 맞고. 답이 O(n^2)다. 그렇다면.

항의할 여지는 상당히 많아 보입니다.


슈도 코드를 저리 쓰면 저도 솔직히 O(n^3)인지 O(n^2)인지 모르므로 답이 없다. 문제 잘 내라. 라고 쓸 거 같습니다.

저 알고리즘 공부 다시 해야 겠어요.

haein   5년 전

djm님 댓글 감사합니다. 그런데 표기의 문제를 떠나서 문제에서 max함수는 ai와 aj사이의 값들과 m값 중에서의 최댓값을 찾는다고 정의 했고 사이라는 말의 사전적의미가 한곳에서 다른곳까지의 거리나 공간을 뜻해서 저는 위와같이 생각했습니다.

chogahui05   5년 전

혹시 문제 원문을 보여주실 수 있나요?

원문이 아니더라도, 문제 내용이 저게 맞다면.. 항의할 여지는 있어보이고요.

보통 알고리듬 시험에서 슈도 코드로 내는 경우, 함수를 생략하는 경우가 있는뎀..

그건 좀 아닌 거 같아요. 익히 알려져 있는 upper_bound나, lower_bound도 아니고.. 그냥 자기가 만든 함수..

익히 알려진 함수라도, 어느 헤더에 포함되어 있는 어느 함수(혹은 메서드)라는 것을 반드시 명시해야 한다고 생각합니다.

ex. 

c++11 algorithm header에 있는 upper_bound()

java8 hashmap 자료구조

그게 없는 경우 논란이 있을 거 같아요.

일단 궁금한 건 슈도에 나온 max 함수 슈도를 보여주실 수 있나요? 아니면 max는 그냥 그렇게만 주어진 것인가요?

전자라면 다행이겠지만 후자라면.. gg쳐야 할 거 같네요.

haein   5년 전

chofahui05 님 댓글 감사합니다. 그냥 출제된 문제 그냥 그대로 타이핑한겁니다. 그냥 문제가 저렇게만 딱 나와있습니다. 

문제. 아래 알고리즘에 대한 복잡도 (big-O)를 구하라. (단, for loop의 조건 검사에 사용된 비교는 무시하라. a1, a2, ..., an은 양의 실수이고 max(aiaj, m)은 ai와 aj사이의 값과 m중에서 가장 큰 값을 찾는 함수이다.)

m <- 0

for i <- 1 to n

     for j <- i + 1 to n

          m <- max(aiaj, m)


이게 문제 원본 그대로입니다.

chogahui05   5년 전

max(aiaj, m)이 구간 [i,j]에 대한 최댓값을 의미하는 것이지요??

그러면 전 gg 치겠습니다. gg 칠 수 밖에 없을 거 같습니다. 전 던질게요.

cpp05013   5년 전

max가 어떻게 구현되어 있는지에 대한 설명이 없으면 이 문제는 답이 없는 것이 맞습니다.

  1. i번째부터 j번째까지 다 둘러보면서 값을 찾는 방식이라면, O(N^3)이 됩니다.
  2. 그런데 이렇게 하지 않아도 값을 찾을 수 있습니다. 간단한 방법으로, max를 처음 불렀을 때 모든 max(aiaj)를 구하고, 그 다음 부를 때부터는 미리 계산해 둔 값을 그대로 가져오면 됩니다. 모든 max(aiaj)를 구하는 건 간단한 다이나믹 프로그래밍으로 해결할 수 있으므로 전체 코드는 O(N^2)가 됩니다.
  3. 한 번 더 꼬아서, 임의의 범위 사이의 최대값을 O(logN)만에 구하는 자료구조가 실제로 존재합니다. 이걸 사용하면 전체 코드는 O(N^2logN)이 됩니다.
  4. max를 이상하게 구현해서 O(N^2)이 걸리면 전체 코드는 O(N^4)가 됩니다. 이런 식으로 생각하면 O(N^2)보다 큰 어떤 시간복잡도라도 답이 될 수 있습니다.
  5. T(max)를 "max가 돌아가는 시간의 최대값"이라고 할 때 O(N^2T(max))를 답이라고 할 수 있느냐 하면 그것도 아닙니다. 다른 입력은 다 1번처럼 하고 max(2 ~ 4)만 이상하게 O(N^3)에 돌아가면 T(max)는 O(N^3)일까요?

댓글을 작성하려면 로그인해야 합니다.