{"id":671,"date":"2020-01-20T10:35:47","date_gmt":"2020-01-20T13:35:47","guid":{"rendered":"https:\/\/micheladrianomedeiros.com.br\/blog\/?p=671"},"modified":"2020-01-20T10:35:49","modified_gmt":"2020-01-20T13:35:49","slug":"javascript-estrutura-e-algoritmos-de-dados-2","status":"publish","type":"post","link":"https:\/\/micheladrianomedeiros.com.br\/blog\/javascript-estrutura-e-algoritmos-de-dados-2\/","title":{"rendered":"JavaScript Estrutura e Algoritmos de Dados #2"},"content":{"rendered":"\n

Regra do Coeficiente:\n\u201cLivre-se das Constantes\u201d<\/strong><\/p>\n\n\n\n

Vamos rever a regra do coeficiente.\nEssa regra \u00e9 a mais f\u00e1cil de entender. Simplesmente necessita que voc\u00ea ignore qualquer\ntamanho de entrada de dados das constantes.<\/p>\n\n\n\n

Coeficientes no Big-O s\u00e3o insignificantes.\nAl\u00e9m disso, a regra mais importante do Big-O s\u00e3o as nota\u00e7\u00f5es.<\/p>\n\n\n\n

Se f(n) \u00e9 O(g(n)), ent\u00e3o kf(n)\n\u00e9 O(g(n)), para qualquer constante k>0.<\/p>\n\n\n\n

Isto significa que ambos 5f(n)\ne f(n) tem a mesma nota\u00e7\u00e3o de Big-O de O(f(n)). Um exemplo de c\u00f3digo com a complexidade\nde O(n):<\/p>\n\n\n\n

function a(n){<\/p>\n\n\n\n

            var\ncount = 0;<\/p>\n\n\n\n

            for(var\ni = 0; i < n; i++){<\/p>\n\n\n\n

                        count+=1;<\/p>\n\n\n\n

            }<\/p>\n\n\n\n

            return count;<\/p>\n\n\n\n

}<\/p>\n\n\n\n

Esse bloco de c\u00f3digo tem f(n)\n= n. Isto adiciona uma contagem de n vezes. Al\u00e9m disso, essa fun\u00e7\u00e3o \u00e9 O(n) de complexidade:<\/p>\n\n\n\n

function a(n){<\/p>\n\n\n\n

            var\ncount = 0;<\/p>\n\n\n\n

            for(var\ni = 0; i < 5*n; i++){<\/p>\n\n\n\n

                        count+=1;<\/p>\n\n\n\n

            }<\/p>\n\n\n\n

            return count;<\/p>\n\n\n\n

}<\/p>\n\n\n\n

Esse bloco tem f(n) = 5n. Isto\nporque executa do 0 ao 5n. Contudo, os dois exemplos ambos t\u00eam a nota\u00e7\u00e3o Big-O\nde O(n).<\/p>\n\n\n\n

Simplesmente, porque se n \u00e9 infinito\nou qualquer outro n\u00famero, as quatros opera\u00e7\u00f5es adicionais s\u00e3o tem significados.<\/p>\n\n\n\n

Isto vai ter uma execu\u00e7\u00e3o de n\nvezes. Quaisquer constantes s\u00e3o insignificantes na nota\u00e7\u00e3o Big-O.<\/p>\n\n\n\n

O c\u00f3digo a seguir apresenta uma\noutra fun\u00e7\u00e3o com uma complexidade linear com uma opera\u00e7\u00e3o adicional na linha 6.<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Esse bloco de c\u00f3digo tem f(n)\n= n+1. H\u00e1 um +3 na \u00faltima opera\u00e7\u00e3o (count+=3). Isto ainda tem a nota\u00e7\u00e3o O(n) do\nBig-O.<\/p>\n\n\n\n

Isto porque a opera\u00e7\u00e3o + 3 n\u00e3o\ndepende da entrada n. Como n pode ser infinito, ela se torna insignificante.<\/p>\n\n\n\n

Regra da Soma: \u201cEleve os\nBig-OS\u201d<\/strong><\/p>\n\n\n\n

A regra da soma \u00e9 intuitiva de\nentender, complexidade temporal pode ser adicionada.<\/p>\n\n\n\n

Imagine um mestre de algoritmo\nque envolve outros dois algoritmos. A nota\u00e7\u00e3o Big-O deste mestre do algoritmo \u00e9\nsimplesmente a soma das outras duas nota\u00e7\u00f5es Big-O.<\/p>\n\n\n\n

Se f(n) \u00e9 O(h(n)) e g(n) \u00e9 O(p(n)),\nent\u00e3o f(n)+g(n) \u00e9 O(h(n)+p(n)).<\/p>\n\n\n\n

\u00c9 importante lembrar de\naplicar a regra do coeficiente depois de aplicar esta regra.<\/p>\n\n\n\n

Segue um c\u00f3digo que apresenta\numa fun\u00e7\u00e3o com dois loops onde suas complexidades devem ser consideradas\nindependentes e ent\u00e3o somadas:<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Nesse exemplo, a linha 4 tem\num f(n)=n e na linha 7 tem um f(n)=5n. Isso resulta em 6n.<\/p>\n\n\n\n

Contudo, quando aplicada a\nregra do coeficiente, o resultado \u00e9 O(n) = n.<\/p>\n","protected":false},"excerpt":{"rendered":"

Regra do Coeficiente: \u201cLivre-se das Constantes\u201d Vamos rever a regra do coeficiente. Essa regra \u00e9 a mais f\u00e1cil de entender. Simplesmente necessita que voc\u00ea ignore qualquer tamanho de entrada de dados das constantes. Coeficientes no Big-O s\u00e3o insignificantes. Al\u00e9m disso, a regra mais importante do Big-O s\u00e3o as nota\u00e7\u00f5es. Se f(n) \u00e9 O(g(n)), ent\u00e3o kf(n) […]<\/p>\n","protected":false},"author":1,"featured_media":374,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[74],"tags":[],"class_list":["post-671","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-javascript"],"_links":{"self":[{"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/posts\/671","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/comments?post=671"}],"version-history":[{"count":1,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/posts\/671\/revisions"}],"predecessor-version":[{"id":674,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/posts\/671\/revisions\/674"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/media\/374"}],"wp:attachment":[{"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/media?parent=671"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/categories?post=671"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/tags?post=671"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}