다중 변수에 대한 큰 효과

Question

입력이 문자열 배열 인 경우 함수의 효율성을 평가하려고합니다. 알고리즘은 항상이 배열의 모든 항목을 반복합니다. 이 배열에 포함 된이 문자열은 가변 길이입니다. 이 초기 for 루프에서는 문자 교체 함수가 각 문자열에서 호출됩니다. 나는 대체 함수가 O (n)이 될 것이라고 믿는다. 여기서 n은 문자열의 길이이다.

큰 오 효율을 평가하는 방법이 혼란 스럽습니다. 만약 n이 배열의 크기라면 적어도 그것이 O (n)이 될 것임을 나는 알고있다. 그러나 가변 문자열 길이의 경우 문자열 교체로 전체 효율성을 어떻게 평가합니까? n을 배열의 크기라고하고 다른 변수를 사용하여 각 문자열의 크기를 나타낼까요?

Answer 1

나는 이것을 (가능한 많은 것) 말하는 두 가지 방법을 본다.

첫 번째 것은 O(N)입니다. 여기에서 N은 총 문자 수입니다.

다른 하나는 O(N*M)입니다. 여기서 N은 문자열의 수이고 M은 문자열 당 평균 문자 수입니다. 이것은 실제로 위의 대답과 같습니다. M = k/N라고 할 수 있으므로 O(N*k/N) 또는 O(k)이됩니다. 여기서 k는 모든 문자열의 총 문자 수입니다.

Answer 2

개인적으로 필자는 입력 데이터의 크기을 통해 효율성을 표현할 것입니다 (배열 길이와 반대 됨). 따라서 입력이 t 바이트 인 경우 실행 시간은 O(t)이됩니다. 여기 t은 모든 문자열의 공통 길이입니다.