{"id":371,"date":"2019-08-07T21:30:31","date_gmt":"2019-08-07T21:30:31","guid":{"rendered":"https:\/\/micheladrianomedeiros.com.br\/blog\/?p=371"},"modified":"2019-08-07T21:30:33","modified_gmt":"2019-08-07T21:30:33","slug":"javascript-estrutura-e-algoritmos-de-dados-1","status":"publish","type":"post","link":"https:\/\/micheladrianomedeiros.com.br\/blog\/javascript-estrutura-e-algoritmos-de-dados-1\/","title":{"rendered":"JavaScript Estrutura e Algoritmos de Dados #1"},"content":{"rendered":"\n

A Cartilha da Anota\u00e7\u00e3o Big-O<\/strong><\/p>\n\n\n\n

A anota\u00e7\u00e3o Big-O mede o pior\ncaso de complexidade de um algoritmo. Na anota\u00e7\u00e3o Big-O, n representa o n\u00famero\nde entradas. A pergunta para o Big-O \u00e9: \u201cO que acontecer\u00e1 se n aproximar do\ninfinito?\u201d<\/p>\n\n\n\n

Quando voc\u00ea implementa um\nalgoritmo, a anota\u00e7\u00e3o Big-O \u00e9 importante para dizer a voc\u00ea o qu\u00e3o eficiente\nest\u00e1 o algoritmo. <\/p>\n\n\n\n

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

O n\u00e3o muda por causa do Data Input.\nConsequentemente, O est\u00e1 referenciado como sendo um tempo constante. Um exemplo\nde um O, \u00e9 o algoritmo que est\u00e1 acessando um item de um array por um index. O(n)\n\u00e9 um tempo linear e aplica para algoritmos que precisa fazer n opera\u00e7\u00f5es dentro\nde um pior cen\u00e1rio.<\/p>\n\n\n\n

Um exemplo de um O(n) \u00e9 um algoritmo que est\u00e1 imprimindo n\u00fameros de 0 a n-1, veja o exemplo:<\/p>\n\n\n\n

function exampleLinear(n){\n\tfor(var i = 0 ; i < n ; i++){\n\t\tconsole.log(i);\n\t}\t\t\n}\n<\/code><\/pre>\n\n\n\n
Similarmente, O(n\u00b2) \u00e9 um tempo quadr\u00e1tico e o O(n\u00b3) \u00e9 um tempo c\u00fabico. Veja os exemplos:<\/p>\n\n\n\n
function exampleQuadratic(n){\n\tfor(var i = 0 ; i < n ; i++){\n\t\tconsole.log(i);\n\t\tfor(var j = i; j < n; j++){\n\t\t\tconsole.log(j);\n\t\t}\n\t}\n}\n\nfunction exampleCubic(n){\n\tfor(var i = 0 ; i < n ; i++){\n\t\tconsole.log(i);\n\t\tfor(var j = i; j < n; j++){\n\t\t\tconsole.log(j);\n\t\t\tfor(var k = j; j < n; j++){\n\t\t\t\tconsole.log(k);\n\t\t\t}\n\t\t}\n\t}\n}\n<\/code><\/pre>\n\n\n\n
O exemplo a seguir \u00e9 uma\npot\u00eancia de 2 em 2 para n. A efici\u00eancia da complexidade do tempo algor\u00edtmico \u00e9\naparentemente grande para grandes n\u00fameros. Apesar de n ser um milh\u00e3o,\nexempleLogarithmic ir\u00e1 imprimir apenas 19 itens porque log2 (1,000,000) =\n19.9315686. Veja o c\u00f3digo: https:\/\/www.calculat.org\/pt\/logaritmos\/logaritmo.html<\/a><\/p>\n\n\n\n
\"\"<\/figure><\/div>\n\n\n\n
Regras da Anota\u00e7\u00e3o Big-O<\/strong><\/p>\n\n\n\n
Vamos representar a\ncomplexidade de um algoritmo com f(n). n representa o n\u00famero de inputs,\nf(n)tempo representa o tempo necess\u00e1rio, e f(n)espa\u00e7o representa o espa\u00e7o (adicional\nde mem\u00f3ria) que o algoritmo precisa. O objetivo de analisar um algoritmo \u00e9\nentender a efici\u00eancia do algoritmo por meio do c\u00e1lculo f(n). Contudo, pode ser\num desafio fazer o c\u00e1lculo f(n). A anota\u00e7\u00e3o Big-O fornece algumas regras para ajudar\no desenvolvedor a resolver o c\u00e1lculo f(n).<\/p>\n\n\n\n
Regra do coeficiente: se f(n)\n\u00e9 O(g(n)), ent\u00e3o kf(n) \u00e9 O(g(n)), para qualquer constante onde k>0. A\nprimeira regra \u00e9 a do coeficiente, a qual elimina coeficientes n\u00e3o relacionados\nao tamanho do input, n. Isto porque o n se aproxima do infinito, e outros\ncoeficientes tornam-se insignificantes. <\/p>\n\n\n\n
Regra da soma: se f(n) \u00e9 O(h(n))\ne g(n) \u00e9 O(p(n)), ent\u00e3o f(n) + g(n) \u00e9 O(h(n)+p(n)). A regra da soma simplesmente\n\u00e9 o resultado da complexidade do tempo, que \u00e9 a soma de dois tempos complexos,\no resultado da anota\u00e7\u00e3o do Big-O \u00e9 tamb\u00e9m a soma de duas diferentes anota\u00e7\u00f5es\nde Big-O.<\/p>\n\n\n\n
Regra do produto: se f(n) \u00e9 O(h(n))\ne g(n) \u00e9 O(p(n)), ent\u00e3o f(n) x g(n) \u00e9 O(h(n) x p(n)). A regra do produto \u00e9 que\no Big-O \u00e9 multiplicado quando tempos complexos s\u00e3o multiplicados. <\/p>\n\n\n\n
Regra transitiva: se f(n) \u00e9 O(g(n))\ne g(n) \u00e9 O(h(n)), ent\u00e3o f(n) \u00e9 O(h(n)). A regra transitiva \u00e9 um simples caminho\nque ao mesmo tempo a complexidade tem o mesmo Big-O.<\/p>\n\n\n\n
Regra polinomial: se f(n) \u00e9 um\npolinomial de grau K, ent\u00e3o f(n) \u00e9 O(n^k). A regra do polinomial \u00e9 quando\ncomplexidade de tempo tem o mesmo grau polinomial do Big-O.<\/p>\n\n\n\n
Regra da pot\u00eancia do Log: log(nk)\n\u00e9 O(log(n)) para qualquer constante onde K>0. Com a regra da pot\u00eancia,\nconstantes dentro da fun\u00e7\u00e3o log s\u00e3o ignoradas pela anota\u00e7\u00e3o Big-O.<\/p>\n\n\n\n
As tr\u00eas primeiras regras e a polinomial s\u00e3o as mais utilizadas.<\/p>\n\n\n\n
JavaScript Data Structures and Algorithms: An Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals<\/a><\/p>\n\n\n\n
https:\/\/amzn.to\/2Kye4xZ<\/a><\/p>\n\n\n\n
#javascript<\/p>\n\n\n","protected":false},"excerpt":{"rendered":"
A Cartilha da Anota\u00e7\u00e3o Big-O A anota\u00e7\u00e3o Big-O mede o pior caso de complexidade de um algoritmo. Na anota\u00e7\u00e3o Big-O, n representa o n\u00famero de entradas. A pergunta para o Big-O \u00e9: \u201cO que acontecer\u00e1 se n aproximar do infinito?\u201d Quando voc\u00ea implementa um algoritmo, a anota\u00e7\u00e3o Big-O \u00e9 importante para dizer a voc\u00ea o […]<\/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":[75],"class_list":["post-371","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-javascript","tag-javascript"],"_links":{"self":[{"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/posts\/371","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=371"}],"version-history":[{"count":2,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/posts\/371\/revisions"}],"predecessor-version":[{"id":376,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/posts\/371\/revisions\/376"}],"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=371"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/categories?post=371"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/micheladrianomedeiros.com.br\/blog\/wp-json\/wp\/v2\/tags?post=371"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}