1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Você provavelmente já ouviu pessoas falarem sobre um algoritmo rápido e eficiente

2
00:00:10,950 --> 00:00:13,090
para a execução de sua tarefa particular,

3
00:00:13,090 --> 00:00:16,110
mas o que exatamente significa isso para um algoritmo para ser rápido ou eficiente?

4
00:00:16,110 --> 00:00:18,580
Bem, ele não está falando de uma medição em tempo real,

5
00:00:18,580 --> 00:00:20,500
como segundos ou minutos.

6
00:00:20,500 --> 00:00:22,220
Isto é porque o hardware do computador

7
00:00:22,220 --> 00:00:24,260
e programa pode variar drasticamente.

8
00:00:24,260 --> 00:00:26,020
Meu programa pode ficar mais lento do que o seu,

9
00:00:26,020 --> 00:00:28,000
porque eu estou correndo em um computador antigo,

10
00:00:28,000 --> 00:00:30,110
ou porque eu acontecer de estar jogando um jogo online

11
00:00:30,110 --> 00:00:32,670
ao mesmo tempo, que se toda a memória hogging meu,

12
00:00:32,670 --> 00:00:35,400
ou eu poderia estar rodando meu programa através de um software diferente

13
00:00:35,400 --> 00:00:37,550
que comunica com o aparelho de forma diferente a um nível baixo.

14
00:00:37,550 --> 00:00:39,650
É como comparar maçãs e laranjas.

15
00:00:39,650 --> 00:00:41,940
Só porque o meu computador mais lento demora mais

16
00:00:41,940 --> 00:00:43,410
do que a sua para dar de volta uma resposta

17
00:00:43,410 --> 00:00:45,510
não significa que você tem o mais eficiente.

18
00:00:45,510 --> 00:00:48,830
>> Então, já que não podemos comparar diretamente os tempos de execução de programas

19
00:00:48,830 --> 00:00:50,140
em segundos ou minutos,

20
00:00:50,140 --> 00:00:52,310
como podemos comparar dois algoritmos diferentes

21
00:00:52,310 --> 00:00:55,030
independentemente do seu hardware ou ambiente de software?

22
00:00:55,030 --> 00:00:58,000
Para criar uma maneira mais uniforme da medição da eficiência algorítmica,

23
00:00:58,000 --> 00:01:00,360
cientistas da computação e matemáticos desenvolveram

24
00:01:00,360 --> 00:01:03,830
conceitos para a medição da complexidade assintótica de um programa

25
00:01:03,830 --> 00:01:06,110
e uma notação chamada 'Ohnotation Big'

26
00:01:06,110 --> 00:01:08,320
para descrever este.

27
00:01:08,320 --> 00:01:10,820
A definição formal é que uma função f (x)

28
00:01:10,820 --> 00:01:13,390
é executado no fim de g (x)

29
00:01:13,390 --> 00:01:15,140
se existir um certo valor (x), x e ₀

30
00:01:15,140 --> 00:01:17,630
uma constante, C, para o qual

31
00:01:17,630 --> 00:01:19,340
f (x) é menor do que ou igual a

32
00:01:19,340 --> 00:01:21,230
que constante vezes g (x)

33
00:01:21,230 --> 00:01:23,190
para todo x maior que x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Mas não se espantam com a definição formal.

35
00:01:25,290 --> 00:01:28,020
O que isso realmente significa em termos menos teóricas?

36
00:01:28,020 --> 00:01:30,580
Bem, é basicamente uma forma de analisar

37
00:01:30,580 --> 00:01:33,580
quão rápido tempo de execução de um programa cresce assintoticamente.

38
00:01:33,580 --> 00:01:37,170
Ou seja, como o tamanho de seus insumos aumenta em direção ao infinito,

39
00:01:37,170 --> 00:01:41,390
digamos, está uma matriz de classificação de tamanho 1000 em comparação com uma matriz de tamanho 10.

40
00:01:41,390 --> 00:01:44,950
Como o tempo de execução do seu programa de crescer?

41
00:01:44,950 --> 00:01:47,390
Por exemplo, imagine contagem do número de caracteres

42
00:01:47,390 --> 00:01:49,350
em uma corda a maneira mais simples

43
00:01:49,350 --> 00:01:51,620
 andando por toda a cadeia

44
00:01:51,620 --> 00:01:54,790
letra por letra e adicionando um a um contador para cada personagem.

45
00:01:55,700 --> 00:01:58,420
Este algoritmo é dito para ser executado em tempo linear

46
00:01:58,420 --> 00:02:00,460
no que diz respeito ao número de caracteres,

47
00:02:00,460 --> 00:02:02,670
'N' na cadeia.

48
00:02:02,670 --> 00:02:04,910
Em suma, ele é executado em O (n).

49
00:02:05,570 --> 00:02:07,290
Por que isso?

50
00:02:07,290 --> 00:02:09,539
Assim, utilizar esta abordagem, o tempo necessário

51
00:02:09,539 --> 00:02:11,300
para atravessar toda a cadeia

52
00:02:11,300 --> 00:02:13,920
é proporcional ao número de caracteres.

53
00:02:13,920 --> 00:02:16,480
Contando o número de caracteres em uma seqüência de 20 caracteres

54
00:02:16,480 --> 00:02:18,580
vai ter o dobro do tempo que for preciso

55
00:02:18,580 --> 00:02:20,330
para contar os caracteres em uma seqüência de 10 caracteres,

56
00:02:20,330 --> 00:02:23,000
porque você tem que olhar para todos os personagens

57
00:02:23,000 --> 00:02:25,740
e cada personagem tem a mesma quantidade de tempo para olhar.

58
00:02:25,740 --> 00:02:28,050
À medida que aumenta o número de caracteres,

59
00:02:28,050 --> 00:02:30,950
o tempo de execução irá aumentar linearmente com o tempo de entrada.

60
00:02:30,950 --> 00:02:33,500
>> Agora, imagine se você decidir que o tempo linear,

61
00:02:33,500 --> 00:02:36,390
O (n), mas não foi rápido o suficiente para você?

62
00:02:36,390 --> 00:02:38,750
Talvez você está armazenando grandes seqüências,

63
00:02:38,750 --> 00:02:40,450
e você não pode pagar o tempo extra que seria necessário

64
00:02:40,450 --> 00:02:44,000
para percorrer todos os seus caracteres de contagem um-por-um.

65
00:02:44,000 --> 00:02:46,650
Então, você decide tentar algo diferente.

66
00:02:46,650 --> 00:02:49,270
E se você acontecer para já armazenar o número de caracteres

67
00:02:49,270 --> 00:02:52,690
na seqüência, digamos, em uma variável chamada 'len'

68
00:02:52,690 --> 00:02:54,210
no início do programa,

69
00:02:54,210 --> 00:02:57,800
antes mesmo armazenado o primeiro personagem na sua corda?

70
00:02:57,800 --> 00:02:59,980
Então, tudo o que você tem que fazer agora para descobrir o comprimento da corda,

71
00:02:59,980 --> 00:03:02,570
é verificar que o valor da variável.

72
00:03:02,570 --> 00:03:05,530
Você não tem que olhar para a própria string, em tudo,

73
00:03:05,530 --> 00:03:08,160
e aceder ao valor de uma variável como len é considerado

74
00:03:08,160 --> 00:03:11,100
uma operação de tempo constante assintoticamente,

75
00:03:11,100 --> 00:03:13,070
ou O (1).

76
00:03:13,070 --> 00:03:17,110
Por que isso? Bem, lembre-se que a complexidade assintótica significa.

77
00:03:17,110 --> 00:03:19,100
O que muda no tempo de execução como o tamanho

78
00:03:19,100 --> 00:03:21,400
de seus insumos cresce?

79
00:03:21,400 --> 00:03:24,630
>> Diga que você estava tentando obter o número de caracteres em uma seqüência maior.

80
00:03:24,630 --> 00:03:26,960
Bem, não importa o quão grande você fazer a seqüência,

81
00:03:26,960 --> 00:03:28,690
até um milhão de caracteres,

82
00:03:28,690 --> 00:03:31,150
tudo o que você tem que fazer para encontrar o comprimento da corda com esta abordagem,

83
00:03:31,150 --> 00:03:33,790
é a leitura do valor da variável de len,

84
00:03:33,790 --> 00:03:35,440
que você já fez.

85
00:03:35,440 --> 00:03:38,200
O comprimento de entrada, isto é, o comprimento da corda que você está tentando encontrar,

86
00:03:38,200 --> 00:03:41,510
não afeta a todos o quão rápido o programa é executado.

87
00:03:41,510 --> 00:03:44,550
Esta parte do seu programa seria executado igualmente rápido em uma cadeia de um caractere

88
00:03:44,550 --> 00:03:46,170
e uma seqüência de mil caracteres,

89
00:03:46,170 --> 00:03:49,140
e é por isso que este programa seria referido como sendo executado em tempo constante

90
00:03:49,140 --> 00:03:51,520
com respeito ao tamanho de entrada.

91
00:03:51,520 --> 00:03:53,920
>> Claro, há uma desvantagem.

92
00:03:53,920 --> 00:03:55,710
Você gasta espaço de memória extra no seu computador

93
00:03:55,710 --> 00:03:57,380
armazenar a variável

94
00:03:57,380 --> 00:03:59,270
e o tempo extra que você leva

95
00:03:59,270 --> 00:04:01,490
para fazer o armazenamento real da variável,

96
00:04:01,490 --> 00:04:03,390
mas o ponto ainda está de pé,

97
00:04:03,390 --> 00:04:05,060
descobrir quanto tempo sua seqüência foi

98
00:04:05,060 --> 00:04:07,600
não depende do comprimento da corda em tudo.

99
00:04:07,600 --> 00:04:10,720
Então, ele é executado em O (1) ou de tempo constante.

100
00:04:10,720 --> 00:04:13,070
Isto certamente não tem de significar

101
00:04:13,070 --> 00:04:15,610
que o código é executado em uma etapa,

102
00:04:15,610 --> 00:04:17,470
mas não importa quantos passos é,

103
00:04:17,470 --> 00:04:20,019
se não se altera com o tamanho das entradas,

104
00:04:20,019 --> 00:04:23,420
ainda é assintoticamente constante que representamos com O (1).

105
00:04:23,420 --> 00:04:25,120
>> Como você provavelmente pode adivinhar,

106
00:04:25,120 --> 00:04:27,940
existem vários grandes runtimes O para medir com algoritmos.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmos são assintoticamente mais lento do que O (n) algoritmos.

108
00:04:32,980 --> 00:04:35,910
Isto é, como o número de elementos (n) aumenta,

109
00:04:35,910 --> 00:04:39,280
eventualmente, O (n) ² algoritmos vai levar mais tempo

110
00:04:39,280 --> 00:04:41,000
que O (n) para executar algoritmos.

111
00:04:41,000 --> 00:04:43,960
Isso não significa que O (n) algoritmos sempre correr mais rápido

112
00:04:43,960 --> 00:04:46,410
do que O (n) ² algoritmos, mesmo no mesmo ambiente,

113
00:04:46,410 --> 00:04:48,080
no mesmo hardware.

114
00:04:48,080 --> 00:04:50,180
Talvez para pequenos tamanhos de entrada,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritmo pode realmente trabalhar mais rápido,

116
00:04:52,900 --> 00:04:55,450
mas, eventualmente, tal como o tamanho de entrada aumenta

117
00:04:55,450 --> 00:04:58,760
para o infinito, a O (n) tempo de execução ² algoritmo

118
00:04:58,760 --> 00:05:02,000
acabará por eclipsar o tempo de execução do algoritmo O (n).

119
00:05:02,000 --> 00:05:04,230
Assim como qualquer função quadrática matemática

120
00:05:04,230 --> 00:05:06,510
 eventualmente ultrapassar qualquer função linear,

121
00:05:06,510 --> 00:05:09,200
não importa o quanto de uma cabeça de iniciar a função linear começa com.

122
00:05:10,010 --> 00:05:12,000
Se você estiver trabalhando com grandes quantidades de dados,

123
00:05:12,000 --> 00:05:15,510
algoritmos que são executados em O (n) ² pode realmente acabar retardando o seu programa,

124
00:05:15,510 --> 00:05:17,770
mas para tamanhos de entrada pequenas,

125
00:05:17,770 --> 00:05:19,420
você provavelmente não vai nem perceber.

126
00:05:19,420 --> 00:05:21,280
>> Outra complexidade assintótica é,

127
00:05:21,280 --> 00:05:24,420
tempo logarítmica, O (log n).

128
00:05:24,420 --> 00:05:26,340
Um exemplo de um algoritmo que executa esse rapidamente

129
00:05:26,340 --> 00:05:29,060
é o algoritmo de busca clássico binário,

130
00:05:29,060 --> 00:05:31,850
para encontrar um elemento em uma lista já ordenada de elementos.

131
00:05:31,850 --> 00:05:33,400
>> Se você não sabe o que busca binária faz,

132
00:05:33,400 --> 00:05:35,170
Eu vou explicar isso para você muito rapidamente.

133
00:05:35,170 --> 00:05:37,020
Vamos dizer que você está olhando para o número 3

134
00:05:37,020 --> 00:05:40,200
neste array de inteiros.

135
00:05:40,200 --> 00:05:42,140
Menciona-se o elemento do meio da matriz

136
00:05:42,140 --> 00:05:46,830
e pergunta: "É o elemento que eu quero superior, igual ou menos do que isso?"

137
00:05:46,830 --> 00:05:49,150
Se for igual, então ótimo. Você encontrou o elemento, e está feito.

138
00:05:49,150 --> 00:05:51,300
Se for maior, então você sabe o elemento

139
00:05:51,300 --> 00:05:53,440
tem de estar no lado direito da matriz,

140
00:05:53,440 --> 00:05:55,200
e você só pode olhar para que, no futuro,

141
00:05:55,200 --> 00:05:57,690
e se ele é menor, então você sabe que tem que estar no lado esquerdo.

142
00:05:57,690 --> 00:06:00,980
Este processo é então repetido com a matriz de menor tamanho

143
00:06:00,980 --> 00:06:02,870
até que o elemento correto seja encontrado.

144
00:06:08,080 --> 00:06:11,670
>> Este poderoso algoritmo corta o tamanho da matriz no meio com cada operação.

145
00:06:11,670 --> 00:06:14,080
Assim, para encontrar um elemento em uma matriz classificada de tamanho 8,

146
00:06:14,080 --> 00:06:16,170
no máximo (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
ou 3 dessas operações,

148
00:06:18,450 --> 00:06:22,260
verificar o elemento central, em seguida, a matriz de corte em meia será exigido,

149
00:06:22,260 --> 00:06:25,670
Considerando uma matriz de tamanho 16 leva (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
ou quatro operações.

151
00:06:27,480 --> 00:06:30,570
Isso é apenas uma operação mais para uma matriz dobrou de tamanho.

152
00:06:30,570 --> 00:06:32,220
A duplicação do tamanho da matriz

153
00:06:32,220 --> 00:06:35,160
aumenta o tempo de execução de apenas um pedaço deste código.

154
00:06:35,160 --> 00:06:37,770
Mais uma vez, o elemento de controlo do meio da lista, então a divisão.

155
00:06:37,770 --> 00:06:40,440
Assim, diz-se para operar em tempo logarítmica,

156
00:06:40,440 --> 00:06:42,440
O (log n).

157
00:06:42,440 --> 00:06:44,270
Mas espere, você diz,

158
00:06:44,270 --> 00:06:47,510
isto não depende de onde na lista o elemento que você está procurando é?

159
00:06:47,510 --> 00:06:50,090
E se o primeiro elemento você olhar passa a ser a pessoa certa?

160
00:06:50,090 --> 00:06:52,040
Então, ele só tem uma operação,

161
00:06:52,040 --> 00:06:54,310
não importa quão grande a lista é.

162
00:06:54,310 --> 00:06:56,310
>> Bem, isso é por que os cientistas de computador têm mais termos

163
00:06:56,310 --> 00:06:58,770
para a complexidade assintótica que refletem o melhor caso

164
00:06:58,770 --> 00:07:01,050
e pior desempenho de um algoritmo.

165
00:07:01,050 --> 00:07:03,320
Mais propriamente, os limites superior e inferior

166
00:07:03,320 --> 00:07:05,090
em tempo de execução.

167
00:07:05,090 --> 00:07:07,660
No melhor dos casos por busca binária, é nossa elemento

168
00:07:07,660 --> 00:07:09,330
ali no meio,

169
00:07:09,330 --> 00:07:11,770
e você obtê-lo em tempo constante,

170
00:07:11,770 --> 00:07:14,240
não importa quão grande o resto da matriz é.

171
00:07:15,360 --> 00:07:17,650
O símbolo utilizado para isso é Ω.

172
00:07:17,650 --> 00:07:19,930
Assim, este algoritmo é dito a correr em Ω (1).

173
00:07:19,930 --> 00:07:21,990
No melhor dos casos, ela encontra o elemento de forma rápida,

174
00:07:21,990 --> 00:07:24,200
não importa quão grande é a matriz,

175
00:07:24,200 --> 00:07:26,050
mas, no pior caso,

176
00:07:26,050 --> 00:07:28,690
que tem de desempenhar (log n) cheques divisão

177
00:07:28,690 --> 00:07:31,030
da matriz para encontrar o elemento certo.

178
00:07:31,030 --> 00:07:34,270
Limites pior superiores são referidos com o grande "O", que você já sabe.

179
00:07:34,270 --> 00:07:38,080
Então, é O (log n), mas Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Uma busca linear, pelo contrário,

181
00:07:40,680 --> 00:07:43,220
em que você anda através de cada elemento da matriz

182
00:07:43,220 --> 00:07:45,170
para encontrar o que você quer,

183
00:07:45,170 --> 00:07:47,420
é a melhor Ω (1).

184
00:07:47,420 --> 00:07:49,430
Mais uma vez, o primeiro elemento que você deseja.

185
00:07:49,430 --> 00:07:51,930
Então, não importa o quão grande é a matriz.

186
00:07:51,930 --> 00:07:54,840
No pior dos casos, é o último elemento na matriz.

187
00:07:54,840 --> 00:07:58,560
Então, você tem que passar por todos os n elementos na matriz para encontrá-lo,

188
00:07:58,560 --> 00:08:02,170
como se você estivesse olhando para um 3.

189
00:08:04,320 --> 00:08:06,030
Então, ele é executado em tempo O (n)

190
00:08:06,030 --> 00:08:09,330
pois é proporcional ao número de elementos na matriz.

191
00:08:10,800 --> 00:08:12,830
>> Mais um símbolo usado é Θ.

192
00:08:12,830 --> 00:08:15,820
Isso pode ser usado para descrever algoritmos onde os casos melhores e piores

193
00:08:15,820 --> 00:08:17,440
são os mesmos.

194
00:08:17,440 --> 00:08:20,390
Este é o caso dos algoritmos seqüência de comprimento que falamos anteriormente.

195
00:08:20,390 --> 00:08:22,780
Isto é, se armazená-lo em uma variável antes

196
00:08:22,780 --> 00:08:25,160
nós armazenamos a corda e acessá-lo mais tarde em tempo constante.

197
00:08:25,160 --> 00:08:27,920
Não importa que número

198
00:08:27,920 --> 00:08:30,130
estamos armazenando nessa variável, nós vamos ter que olhar para ele.

199
00:08:33,110 --> 00:08:35,110
O melhor caso é, olhamos para ele

200
00:08:35,110 --> 00:08:37,120
e encontrar o comprimento da corda.

201
00:08:37,120 --> 00:08:39,799
Assim Ω (1), ou melhor, caso o tempo constante.

202
00:08:39,799 --> 00:08:41,059
O pior caso é,

203
00:08:41,059 --> 00:08:43,400
olharmos para ele e encontrar o comprimento da corda.

204
00:08:43,400 --> 00:08:47,300
Assim, ó (1) ou constante de tempo no pior caso.

205
00:08:47,300 --> 00:08:49,180
Então, uma vez que o melhor caso e pior dos casos são os mesmos,

206
00:08:49,180 --> 00:08:52,520
isso pode ser dito para ser executado em tempo Θ (1).

207
00:08:54,550 --> 00:08:57,010
>> Em resumo, temos boas maneiras de raciocinar sobre a eficiência códigos

208
00:08:57,010 --> 00:09:00,110
sem saber nada sobre o tempo do mundo real que tomam para correr,

209
00:09:00,110 --> 00:09:02,270
que é afetado por muitos fatores externos,

210
00:09:02,270 --> 00:09:04,190
incluindo hardware diferentes, software,

211
00:09:04,190 --> 00:09:06,040
ou as especificidades do seu código.

212
00:09:06,040 --> 00:09:08,380
Além disso, ela nos permite raciocinar bem sobre o que vai acontecer

213
00:09:08,380 --> 00:09:10,180
quando o tamanho dos aumentos de entradas.

214
00:09:10,180 --> 00:09:12,490
>> Se você estiver executando em O (n) algoritmo ²,

215
00:09:12,490 --> 00:09:15,240
ou pior, um O (2 ⁿ) algoritmo,

216
00:09:15,240 --> 00:09:17,170
um dos mais rápidos tipos de cultivo,

217
00:09:17,170 --> 00:09:19,140
você vai realmente começar a notar a desaceleração

218
00:09:19,140 --> 00:09:21,220
quando você começar a trabalhar com grandes quantidades de dados.

219
00:09:21,220 --> 00:09:23,590
>> Essa é a complexidade assintótica. Obrigado.