1
A
답변
3
실제로 압축을 수행하지 않고도 LZ 복잡도를 계산할 수 있지만 입력 데이터를 LZ 압축 할 때처럼 계산이 많이 발생합니다. 예를 들어 calculating Lempel-Ziv (LZ) complexity (aka sequence complexity) of a binary string을 참조하십시오. 여기서 대답 중 하나는 LZ 복잡도를 계산하기위한 (비 압축) 코드입니다.
관련 문제
- 1. 시간 복잡도 알고리즘 분석
- 2. 2^n 복잡도 알고리즘
- 3. O 표기법의 알고리즘 복잡도 순서
- 4. O (fib n) 복잡도 알고리즘?
- 5. 은행가 알고리즘 계산 시간 복잡도
- 6. 연결된 목록의 알고리즘 복잡도 분석
- 7. Fleury 알고리즘의 시간 복잡도
- 8. 알고리즘 복잡도 질문 >> g & F> g
- 9. 공간 복잡도
- 10. valarray 복잡도
- 11. 스택 복잡도
- 12. 프로그램의 시간 복잡도
- 13. while 루프의 시간 복잡도
- 14. 최악의 시간 복잡도
- 15. 이진 트리 탐색의 복잡도
- 16. HashMap get/put 복잡도
- 17. 알고리즘의 시간 복잡도
- 18. 시간 복잡도 무역 오프는
- 19. 다항식 곱셈의 복잡도 감소
- 20. 컴파일러의 점근 복잡도
- 21. 시간 복잡도 power()
- 22. 재귀 알고리즘의 시간 복잡도
- 23. Java ArrayList의 시간 복잡도
- 24. 데이터베이스 쿼리 시간 복잡도
- 25. 정렬 알고리즘의 시간 복잡도
- 26. 시간 복잡도 감소
- 27. 다차원 해시의 공간 복잡도
- 28. Java 알고리즘에 대한 복잡도 클래스를 어떻게 찾을 수 있습니까?
- 29. 로그 알고리즘을위한 빅 오 복잡도
- 30. Recushive 알고리즘의 시간 복잡도 계산
감사! 그러나 압축을 생성하고 복잡성을 계산하는 다른 방법이 있습니까? – lexeme
나는 그렇게 생각한다; 표준 LZ 압축기를 실행하고 사전에 이미있는 문자열의 일부가 아닌 비트가 나타날 때마다 카운터를 증가 시키면 입력의 LZ 복잡도가 높아집니다. 아니면 적어도 그 근사치; 실용적인 LZ 압축기는 근사치를 만듭니다. –