PS: Eu sei calcular O (...) se o código for fornecido. Aqui não conheço o algoritmo da função de divisão.
java strings java8
— tezz
fonte
Possível duplicata de O que é O (...) e como faço para calcular?
— gnat
Desde que eu não sei a algo de função split, eu não acho que essa é uma pergunta duplicado @gnat
— Tezz
Respostas:
7
A complexidade dependerá do regex que você usa para fazer a divisão. (Sim, o argumento que você fornece para String.split (...) é um regex!)
Para o seu exemplo, será O(N)onde Nestá o número de caracteres na String de entrada.
O algoritmo de divisão é bastante simples, com base em uma implementação de regex existente. Uma descrição de alto nível é:
Compile o regex e crie um correspondente
Itere sobre a sequência:
Use Matcher.find(...)para encontrar o próximo limite de palavras
Use String.substring para extrair a palavra
Adicionar palavra a uma lista de strings
Converta a lista de strings em uma matriz de strings.
A busca pelas quebras entre "palavras" será O(N)ou mais complexa, dependendo da regex (a findchamada). A construção da lista, matriz de resultados e substrings será O(N)no pior caso.
Os detalhes precisos estão no código-fonte, que você pode encontrar usando o Google. (Procure "java.lang.String" source, escolha um e, em seguida, faça um drill down para a versão do Java em que você está interessado. Ou pesquise os arquivos no arquivo ZIP do código-fonte incluído na instalação do JDK)
— Stephen C
fonte
3
É O (n) em seus casos específicos, onde você está dividindo por separadores de 1/0 caracteres. Em geral, é O (n + k) com um separador de caracteres k, pode ser implementado usando o algoritmo KMP. A divisão de cadeia de caracteres Java também aceita regexes como separadores; nesse caso, sua complexidade depende do algoritmo de correspondência que está sendo usado. Um algoritmo comum de correspondência de expressões regulares é o algoritmo Thompson NFA.
— VinyleEm
fonte
Ao utilizar nosso site, você reconhece que leu e compreendeu nossa Política de Cookies e nossa Política de Privacidade.